Permutive one-way cellular automata and the finiteness problem for automaton groups - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

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 (625.36 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

  • HAL Id : hal-01436460 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More