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

Martin Delacourt 1, * Nicolas Ollinger 1
* Auteur correspondant
1 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans
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.
Keywords : reset Mealy automata one-sided cellular automata permutive cellular automata periodicity problem reversible computation
Type de document :
Communication dans un congrès
Computability in Europe, Jun 2017, Turku, Finland. Proceedings CiE 2017 in Turku, 2017, 〈http://math.utu.fi/cie2017/〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal-univ-orleans.archives-ouvertes.fr/hal-01436460
Contributeur : Martin Delacourt <>
Soumis le : mardi 14 mars 2017 - 12:52:39
Dernière modification le : vendredi 26 octobre 2018 - 10:41:15
Document(s) archivé(s) le : jeudi 15 juin 2017 - 13:55:39

Fichier

pocafpag.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01436460, version 2

Collections

UNIV-ORLEANS

Citation

Martin Delacourt, Nicolas Ollinger. Permutive one-way cellular automata and the finiteness problem for automaton groups. Computability in Europe, Jun 2017, Turku, Finland. Proceedings CiE 2017 in Turku, 2017, 〈http://math.utu.fi/cie2017/〉. 〈hal-01436460v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

192

Téléchargements de fichiers

150

Contact

SCD de l'Université d'Orléans
hal@listes.univ-orleans.fr