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.
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 : mercredi 16 mai 2018 - 12:14:01
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

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〉

Partager

Métriques

Consultations de la notice

183

Téléchargements de fichiers

141