%0 Conference Proceedings
%T Group-Walking Automata
%+ Universidad de Chile = University of Chile [Santiago] (UCHILE)
%+ University of Turku
%A Salo, Ville
%A Törmä, Ilkka
%Z Part 2: Regular Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Turku, Finland
%Y Jarkko Kari
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-9099
%P 224-237
%8 2015-06-08
%D 2015
%R 10.1007/978-3-662-47221-7_17
%K Group-walking automaton
%K Torsion group
%K Periodic group
%K Multi-headed automaton
%K Subshift
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01442475/document
%2 https://inria.hal.science/hal-01442475/file/338243_1_En_17_Chapter.pdf
%L hal-01442475
%U https://inria.hal.science/hal-01442475
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9099
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA