Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 metadata

Cited literature [16 references]  Display  Hide  Download

https://hal-univ-orleans.archives-ouvertes.fr/hal-01436460
Contributor : Nicolas Ollinger Connect in order to contact the contributor
Submitted on : Monday, January 16, 2017 - 2:17:34 PM
Last modification on : Tuesday, October 12, 2021 - 5:20:40 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

134

Files downloads

66