Two-dimensional languages and cellular automata
This article studies cellular automata (CA) through the new point of view of the picture language that they generate, that is, the set of blocks appearing in the half-planes that the evolution of bi-infinite configurations draw (space-time diagrams). The authors define the so-called factorial-local CA, whose language can be defined from a particular (finite) family of allowed blocks of some fixed size.NEWLINENEWLINEThey remark that this fixed size can always be taken to be the diameter, and that this class corresponds to the class of CA whose all (or one) sufficiently large traces (that is, sets of infinite words appearing in columns of the space-time diagrams) are subshifts of finite type. This class was studied in [\textit{P. Di Lena}, J. Cell. Autom. 2, No. 2, 121--129 (2007; Zbl 1135.68488)]. In particular, it includes nilpotent CA and is included in those having the shadowing property (see [\textit{P. Kůrka}, Topological and symbolic dynamics. Cours Spécialisés (Paris) 11. Paris: Société Mathématique de France (2003; Zbl 1038.37011)]); they give a counter-example to the converse, as well as one factorial-local CA with one trace not of finite type.NEWLINENEWLINEThe main result is the construction of a suitable (complicated) finite automaton that gives the decidability of whether a CA of a given radius corresponds to a given factorial-local language, from which is derived that the property of being factor-local is undecidable -thanks to the above characterization, this appears to be a particular case of [\textit{P. di Lena}, in: Proc. of the 4th IFIP Int. Conf. on Theor, Comput. Sci., 185--196 (2006)].
- A note on decidability of cellularity
- Towards a Rice Theorem on Traces of Cellular Automata
- A comparison of finite and cellular automata
- Formal languages and global cellular automaton behavior
- Decidability and undecidability in cellular automata
- Ultimate traces of cellular automata
- Machines, Computations, and Universality
- Mathematical Foundations of Computer Science 2004
- scientific article; zbMATH DE number 4195191
- scientific article; zbMATH DE number 4215382
- An Introduction to Symbolic Dynamics and Coding
- Dynamical behaviour of Coven's aperiodic cellular automata
- Equicontinuity and sensitivity of nondeterministic cellular automata
- Languages, equicontinuity and attractors in cellular automata
- Multiplicities of covers for sofic shifts
- On Complexity of Two Dimensional Languages Generated by Transducers
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Complexity of two-dimensional patterns
- From one-dimensional to two-dimensional cellular automata
- On Some Classes of 2D Languages and Their Relations
- Finite State Automata Representing Two-Dimensional Subshifts
- Decidable Properties of 2D Cellular Automata
- Local rule distributions, language complexity and non-uniform cellular automata
- scientific article; zbMATH DE number 1156461 (Why is no real title available?)
- scientific article; zbMATH DE number 2150293 (Why is no real title available?)
- A Language for Particle Interactions in Rule 54 and Other Cellular Automata
- TRANSITIVITY IN TWO-DIMENSIONAL LOCAL LANGUAGES DEFINED BY DOT SYSTEMS
- A note on decidability of cellularity
- Two-dimensional cellular automata
This page was built for publication: Two-dimensional languages and cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909191)
