A characterization of p-automatic sequences as columns of linear cellular automata

DOI10.1016/J.AAM.2014.10.002MaRDI QIDQ477771zbMATH OpenOpenAlexFDO

Authors Reem Yassawi, Eric Rowland

Publication date 9 December 2014

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.6008

zbMATH Keywords

memoryautomatic sequencefinite fieldChristol's theoremsubstitution dynamical systemfactor maplinear cellular automata

Mathematics Subject Classification ID

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

Abstract: We show that a sequence over a finite field $mathbb{F}_q$ of characteristic $p$ is $p$-automatic if and only if it occurs as a column of the spacetime diagram, with eventually periodic initial conditions, of a linear cellular automaton with memory over $mathbb{F}_q$. As a consequence, the subshift generated by a length-$p$ substitution can be realized as a topological factor of a linear cellular automaton.

Recommendations

• Characteristic Sequences of the Sets of Sums of Squares as Columns of Cellular Automata
• Automaticity of double sequences generated by one-dimensional linear cellular automata
• Linear cellular automata and recurring sequences in finite fields
• Linear cellular automata and recurring sequences in finite fields
• On the \(N\)th linear complexity of automatic sequences
• A characterization of multidimensional \(S\)-automatic sequences
• Automorphisms of transition graphs for linear cellular automata
• Automaticity and invariant measures of linear cellular automata
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Construction of some nonautomatic sequences by cellular automata

Cites work

• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3513916 (Why is no real title available?)
• Additive cellular automata and algebraic series
• Algebraic functions over finite fields
• Algebraic properties of cellular automata
• Automatic Sequences
• Automaticity of double sequences generated by one-dimensional linear cellular automata
• Embedding Bratteli–Vershik systems in cellular automata
• Endomorphisms and automorphisms of the shift dynamical system
• Local nested structure in Rule 30
• Substitution dynamical systems. Spectral analysis
• Substitutions in dynamics, arithmetics and combinatorics
• Suites algébriques, automates et substitutions
• Uniform tag sequences

Cited in

(9)

• A two-valued recurrent double sequence that is not automatic
• Automatic congruences for diagonals of rational functions
• F_p-affine recurrent n-dimensional sequences over F_q are p-automatic
• Column representation of Sturmian words in cellular automata
• From combinatorial games to shape-symmetric morphisms
• Characteristic Sequences of the Sets of Sums of Squares as Columns of Cellular Automata
• Automaticity and invariant measures of linear cellular automata
• Profinite automata
• Construction of some nonautomatic sequences by cellular automata

Describes a project that uses

Uses Software

• BijectiveRules

This page was built for publication: A characterization of \(p\)-automatic sequences as columns of linear cellular automata

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