Plane-Walking Automata
: Salo V, Torma I
: 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
: 2015
: Lecture Notes in Computer Science
: Cellular automata and discrete complex systems
: CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS (AUTOMATA 2014)
: Lect Notes Computer Sc
: Lecture notes in computer science
: 8996
: 135
: 148
: 14
: 978-3-319-18812-6
: 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.