Automaticity of double sequences generated by one-dimensional linear cellular automata

DOI10.1016/S0304-3975(96)00298-8MaRDI QIDQ1389657zbMATH OpenFDO

Authors D. Massart

Publication date 30 June 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(96)00298-8

zbMATH Keywords

\(k\)-automatic sequencelinear one-dimensional cellular automata

Mathematics Subject Classification ID

Automata sequences (11B85) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Review text

A sequence \(n\mapsto u(n)\) of elements of a finite set is said to be \(k\)-automatic, if restricting the domain to congruence classes modulo powers of \(k\) yield only finitely many subsequences. The authors consider double (i.e., spatio-temporal) sequences generated by linear one-dimensional cellular automata over a modular domain, to which the notion of automaticity is readily generalized. The authors characterize completely the automatic sequences, proving (among other things) that a sequence is \(k\)-automatic if and only if \(R(X^k)=R(X)^k\), where \(R(X)\) is some power of the generating polynomial of the automaton.

Recommendations

• A characterization of \(p\)-automatic sequences as columns of linear cellular automata
• Linear cellular automata, finite automata and Pascal's triangle
• Automatic sequences
• Enumeration and automatic sequences
• Automaticity of rational functions

Cites work

• AUTOMATIC MAPS ON A SEMIRING WITH DIGITS
• Cellular automata, matrix substitutions and fractals
• Endomorphisms and automorphisms of the shift dynamical system
• Finite automata in number theory
• Folds! III: More morphisms
• Fractal patterns in Gaussian and Stirling number tables
• scientific article; zbMATH DE number 4139309 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 4021221 (Why is no real title available?)
• scientific article; zbMATH DE number 4065109 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• Linear cellular automata, finite automata and Pascal's triangle
• Logic and p-recognizable sets of integers
• On the base-dependence of sets of numbers recognizable by finite automata
• Semigroups, Presburger formulas, and languages
• Suites algébriques, automates et substitutions
• The ring of k-regular sequences
• Uniform tag sequences

Cited in

(19)

• Periodic character sequences where identifying two characters strictly reduces the period
• Automaticity of rational functions
• The density of 0's in recurrence double sequences.
• Construction of some nonautomatic sequences by cellular automata
• Limit sets of automatic sequences.
• Linear cellular automata, finite automata and Pascal's triangle
• How to prove that a sequence is not automatic
• Random matrix products and applications to cellular automata
• The distribution of elements in automatic double sequences
• Linearization of automatic arrays and weave specifications
• An analogue of Cobham’s theorem for fractals
• Rational digit systems over finite fields and Christol's theorem
• A characterization of \(p\)-automatic sequences as columns of linear cellular automata
• Automaticity and invariant measures of linear cellular automata
• From combinatorial games to shape-symmetric morphisms
• Linear recurrent double sequences with constant border in \(M_2(\mathbb F_2)\) are classified according to their geometric content
• SELF-SIMILAR STRUCTURE OF RESCALED EVOLUTION SETS OF CELLULAR AUTOMATA II
• Automatic maps in exotic numeration systems
• On subword decomposition and balanced polynomials

This page was built for publication: Automaticity of double sequences generated by one-dimensional linear cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1389657)