Permutive one-way cellular automata and the finiteness problem for automaton groups - Archive ouverte HAL Access content directly
Conference Papers Year : 2017

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

(1) , (1)
1

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.
Fichier principal
Vignette du fichier
pocafpag.pdf (316.18 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01436460 , version 1 (16-01-2017)
hal-01436460 , version 2 (14-03-2017)

Identifiers

Cite

Martin Delacourt, Nicolas Ollinger. Permutive one-way cellular automata and the finiteness problem for automaton groups. Computability in Europe, Jun 2017, Turku, Finland. ⟨10.1007/978-3-319-58741-7_23⟩. ⟨hal-01436460v2⟩
386 View
544 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More