Permutive one-way cellular automata and the finiteness problem for automaton groups - Université d'Orléans Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

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

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
395 Consultations
579 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More