A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Group-Walking Automata
Tekijät: Ville Salo, Ilkka Törmä
Toimittaja: Jarkko Kari
Konferenssin vakiintunut nimi: International Workshop on Cellular Automata and Discrete Complex Systems
Kustannuspaikka: Berlin
Julkaisuvuosi: 2015
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Cellular Automata and Discrete Complex Systems
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 9099
Aloitussivu: 224
Lopetussivu: 237
Sivujen määrä: 14
ISBN: 978-3-662-47220-0
eISBN: 978-3-662-47221-7
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-662-47221-7_17
Verkko-osoite: http://link.springer.com/chapter/10.1007%2F978-3-662-47221-7_17
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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
