Plane-Walking Automata




Salo V, Torma I

Teijiro Isokawa,Katsunobu Imai,Nobuyuki Matsui,Ferdinand Peper,Hiroshi Umeo

PublisherSprinder-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

DOIhttps://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.




Last updated on 2024-26-11 at 17:32