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

DOI10.1007/978-3-319-58741-7_23zbMATH Open1489.68146OpenAlexW2612951341MaRDI QIDQ2011658FDOQ2011658

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Generic properties in some classes of automaton groups
• 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)