A1 Refereed original research article in a scientific journal
Independent finite automata on Cayley graphs
Authors: Salo V, Torma I
Publisher: SPRINGER
Publishing place: GZ DORDRECHT
Publication year: 2017
Journal: Natural Computing
Journal name in source: NATURAL COMPUTING
Journal acronym: NAT COMPUT
Volume: 16
Issue: 3
First page : 411
Last page: 426
Number of pages: 16
ISSN: 1567-7818
eISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-017-9613-6
Abstract
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.
UTU Research Portal