A3 Refereed book chapter or chapter in a compilation book
Plane-Walking Automata
Authors: Salo V, Torma I
Editors: Teijiro Isokawa,Katsunobu Imai,Nobuyuki Matsui,Ferdinand Peper,Hiroshi Umeo
Publisher: Sprinder-Verlag New York, MS Ingrid Cunningham, 175 Fifth Ave, New York, NY 10010 USA
Publication year: 2015
Journal: Lecture Notes in Computer Science
Book title : Cellular automata and discrete complex systems
Journal name in source: CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS (AUTOMATA 2014)
Journal acronym: Lect Notes Computer Sc
Series title: Lecture notes in computer science
Volume: 8996
First page : 135
Last page: 148
Number of pages: 14
ISBN: 978-3-319-18812-6
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-18812-6_11
In this article, we study classes of multidimensional sub-shifts defined by multihead finite automata, in particular the hierarchy of classes of subshifts defined as the number of heads grows. The hierarchy collapses on the third level, where all co-recursively enumerable subshifts are obtained in every dimension. We also compare these classes to SFTs and sofic shifts. We are unable to separate the second and third level of the hierarchy in one and two dimensions, and suggest a related open problem for two-counter machines.
