On the conjugacy problem of cellular automata

DOI10.1016/j.ic.2020.104531zbMath1459.37013arXiv1906.00796OpenAlexW2947207802MaRDI QIDQ2201790

Joonatan Jalonen, Jarkko Kari

Publication date: 17 September 2020

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

undecidabilityconjugacycellular automata

Mathematics Subject Classification ID

Topological and differentiable equivalence, conjugacy, moduli, classification of dynamical systems (37C15) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15)

Cites Work

• Unnamed Item
• Unnamed Item
• Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
• Periodic points for onto cellular automata
• Reversibility and surjectivity problems of cellular automata
• Combinatorial constructions associated to the dynamics of one-sided cellular automata.
• Classification of subshifts of finite type
• Permutive one-way cellular automata and the finiteness problem for automaton groups
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• On the Limit Sets of Cellular Automata
• Finite entropy for multidimensional cellular automata
• Periodicity and Immortality in Reversible Computing
• The Nilpotency Problem of One-Dimensional Cellular Automata
• Linear sampling and the ∀∃∀ case of the decision problem
• Languages, equicontinuity and attractors in cellular automata
• Textile systems for endomorphisms and automorphisms of the shift
• Conjugacy of One-Dimensional One-Sided Cellular Automata is Undecidable
• Shifting and Lifting of Cellular Automata
• Endomorphisms and automorphisms of the shift dynamical system

This page was built for publication: On the conjugacy problem of cellular automata