A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Independent finite automata on Cayley graphs
Tekijät: Salo V, Torma I
Kustantaja: SPRINGER
Kustannuspaikka: GZ DORDRECHT
Julkaisuvuosi: 2017
Journal: Natural Computing
Tietokannassa oleva lehden nimi: NATURAL COMPUTING
Lehden akronyymi: NAT COMPUT
Vuosikerta: 16
Numero: 3
Aloitussivu: 411
Lopetussivu: 426
Sivujen määrä: 16
ISSN: 1567-7818
eISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-017-9613-6
Tiivistelmä
In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of finite automata with multiple independent heads that walk on Cayley graphs, called group-walking automata, 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, and those on which the head hierarchy is infinite.
In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of finite automata with multiple independent heads that walk on Cayley graphs, called group-walking automata, 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, and those on which the head hierarchy is infinite.
Turun yliopiston Tutkimustietojärjestelmän portaali