Group-Walking Automata

Abstract : In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of multi-headed finite automata that walk on Cayley graphs, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines.
Type de document :
Communication dans un congrès
Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Lecture Notes in Computer Science, LNCS-9099, pp.224-237, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_17〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01442475
Contributeur : Hal Ifip <>
Soumis le : vendredi 20 janvier 2017 - 16:09:23
Dernière modification le : lundi 23 janvier 2017 - 13:58:18
Document(s) archivé(s) le : vendredi 21 avril 2017 - 15:59:43

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Ville Salo, Ilkka Törmä. Group-Walking Automata. Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Lecture Notes in Computer Science, LNCS-9099, pp.224-237, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_17〉. 〈hal-01442475〉

Partager

Métriques

Consultations de la notice

24

Téléchargements de fichiers

6