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

Abstract : The decidability of the finiteness problem for automaton groups is a well-studied open question on Mealy automata. We connect this question of algebraic nature to the periodicity problem of one-way cellular automata, a dynamical question known to be undecidable in the general case. We provide a first undecidability result on the dynamics of one-way permutive cellular automata, arguing in favor of the undecidability of the finiteness problem for reset Mealy automata.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-univ-orleans.archives-ouvertes.fr/hal-01436460
Contributor : Nicolas Ollinger <>
Submitted on : Monday, January 16, 2017 - 2:17:34 PM
Last modification on : Thursday, January 17, 2019 - 3:10:02 PM
Long-term archiving on : Monday, April 17, 2017 - 2:15:39 PM

File

pocafpag.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01436460, version 1

Citation

Martin Delacourt, Nicolas Ollinger. Permutive one-way cellular automata and the finiteness problem for automaton groups. 2017. ⟨hal-01436460v1⟩

Share

Metrics

Record views

133

Files downloads

66