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

Rowland, Eric and Yassawi, Reem (2015). A characterization of p-automatic sequences as columns of linear cellular automata. Advances in Applied Mathematics, 63 pp. 68–89.

DOI: https://doi.org/10.1016/j.aam.2014.10.002

Abstract

We show that a sequence over a finite field 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 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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 67097
• Item Type
• Journal Item
• ISSN
• 0196-8858
• Project Funding Details

• Funded Project Name	Project ID	Funding Body
  Discovery Grant	Not Set	NSERC

• Keywords
• Automatic sequences; Linear cellular automata with memory; Christol's theorem; Substitution dynamical systems; Factor maps
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2014 Elsevier Inc.
• Depositing User
• Reem Yassawi