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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01442475
Contributor : Hal Ifip <>
Submitted on : Friday, January 20, 2017 - 4:09:23 PM
Last modification on : Wednesday, February 13, 2019 - 6:30:03 PM
Long-term archiving on : Friday, April 21, 2017 - 3:59:43 PM

File

338243_1_En_17_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Ville Salo, Ilkka Törmä. Group-Walking Automata. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. pp.224-237, ⟨10.1007/978-3-662-47221-7_17⟩. ⟨hal-01442475⟩

Share

Metrics

Record views

37

Files downloads

50