Permutive one-way cellular automata and the finiteness problem for automaton groups

DOI10.1007/978-3-319-58741-7_23zbMath1489.68146OpenAlexW2612951341MaRDI QIDQ2011658

Martin Delacourt, Nicolas Ollinger

Publication date: 4 August 2017

Full work available at URL: https://hal-univ-orleans.archives-ouvertes.fr/hal-01436460v2/document

zbMATH Keywords

reversible computationone-sided cellular automataperiodicity problempermutive cellular automatareset Mealy automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

An automaton group with undecidable order and Engel problems, On the conjugacy problem of cellular automata, Automaton (Semi)groups: Wang Tilings and Schreier Tries, Generic properties in some classes of automaton groups

Cites Work

• Automaton semigroups: the two-state case.
• Bulking II: Classifications of cellular automata
• Logic and \(p\)-recognizable sets of integers
• Combinatorial constructions associated to the dynamics of one-sided cellular automata.
• Expansive invertible onesided cellular automata
• Theory of cellular automata: a survey
• The conjugacy problem in automaton groups is not solvable.
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Implementing Computations in Automaton (Semi)groups
• Prevalence of odometers in cellular automata
• Periodicity and Immortality in Reversible Computing
• The Nilpotency Problem of One-Dimensional Cellular Automata
• THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
• Endomorphisms and automorphisms of the shift dynamical system