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 :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-univ-orleans.archives-ouvertes.fr/hal-01436460
Contributor : Martin Delacourt <>
Submitted on : Tuesday, March 14, 2017 - 12:52:39 PM
Last modification on : Tuesday, November 19, 2019 - 4:48:10 PM
Long-term archiving on : Thursday, June 15, 2017 - 1:55:39 PM

File

pocafpag.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01436460, version 2

Citation

Martin Delacourt, Nicolas Ollinger. Permutive one-way cellular automata and the finiteness problem for automaton groups. Computability in Europe, Jun 2017, Turku, Finland. ⟨hal-01436460v2⟩

Share

Metrics

Record views

266

Files downloads

336