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

DOI10.1016/J.AAM.2014.10.002zbMATH Open1326.37008arXiv1209.6008OpenAlexW1978671960MaRDI QIDQ477771FDOQ477771

Reem Yassawi, Eric Rowland

Publication date: 9 December 2014

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Endomorphisms and automorphisms of the shift dynamical system
• Algebraic functions over finite fields
• Suites algébriques, automates et substitutions
• Title not available (Why is that?)
• Automatic Sequences
• Uniform tag sequences
• Substitutions in dynamics, arithmetics and combinatorics
• Substitution dynamical systems. Spectral analysis
• Automaticity of double sequences generated by one-dimensional linear cellular automata
• Algebraic properties of cellular automata
• Embedding Bratteli–Vershik systems in cellular automata
• Title not available (Why is that?)
• Additive cellular automata and algebraic series

Cited In (7)

• A two-valued recurrent double sequence that is not automatic
• Automatic congruences for diagonals of rational functions
• From Combinatorial Games to Shape-Symmetric Morphisms
• Automaticity and Invariant Measures of Linear Cellular Automata
• Column representation of Sturmian words in cellular automata
• Characteristic Sequences of the Sets of Sums of Squares as Columns of Cellular Automata
• Construction of some nonautomatic sequences by cellular automata

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)