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

DOI10.1007/978-3-319-58741-7_23MaRDI QIDQ2011658zbMATH OpenOpenAlexFDO

Authors 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) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Recommendations

• scientific article; zbMATH DE number 1166283
• A generalization of cellular automata over groups
• scientific article; zbMATH DE number 1537527
• scientific article; zbMATH DE number 3273200
• scientific article; zbMATH DE number 599365
• Cellular automata on group sets and the uniform Curtis-Hedlund-Lyndon theorem
• scientific article; zbMATH DE number 1376768
• scientific article; zbMATH DE number 3266641
• The word problem for finitary automaton groups
• Some problems on groups of finite automatic permutations

Cites work

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

Cited in

(6)

• 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
• scientific article; zbMATH DE number 5582847 (Why is no real title available?)
• The finiteness problem for automaton semigroups is undecidable.

This page was built for publication: Permutive one-way cellular automata and the finiteness problem for automaton groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011658)