Automatic sequences can be defined by DFAs with output (DFAO) in two natural ways. We propose to consider the minimal size of a corresponding DFAO as the complexity measure of the automatic sequence, for both variants. This paper compares these complexity measures and investigates their properties, such as the relationships with kernel and morphic sequences. There exist automatic sequences for which the one complexity is exponentially greater than the other one, in both directions. For both complexity measures we investigate the effect of taking basic operations on sequences, like removing or adding an initial element, combining sequences, or taking arithmetic subsequences, and observe that these operations may increase the complexity at most polynomially. For periodic sequences we give sharp bounds for both complexity measures.

MAGMA is a new software system for computational algebra, number theory and geometry whose design is centred on the concept of algebraic structure (magma). The use of algebraic structure as a design paradigm provides a natural strong typing mechanism. Further, structures and their morphisms appear in the language as first class objects. Standard mathematical notions are used for the basic data types. The result is a powerful, clean language which deals with objects in a mathematically rigorous manner. The conceptual and implementation ideas behind MAGMA will be examined in this paper. This conceptual base differs significantly from those underlying other computer algebra systems.

Article Free Access Share on Computations with finitely generated modules over Dedekind rings Authors: Wieb Bosma Department of Pure Mathematics, University of Sydney, Sydney, NSW 2006, Australia Department of Pure Mathematics, University of Sydney, Sydney, NSW 2006, AustraliaView Profile , Michael Pohst Mathematisches Institut, Heinrich-Heine-Universität, 4000 Düsseldorf, Germany Mathematisches Institut, Heinrich-Heine-Universität, 4000 Düsseldorf, GermanyView Profile Authors Info & Claims ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computationJune 1991 Pages 151–156https://doi.org/10.1145/120694.120714Published:01 June 1991Publication History 9citation208DownloadsMetricsTotal Citations9Total Downloads208Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF