A3 Vertaisarvioitu kirjan tai muun kokoomateoksen osa
Plane-Walking Automata
Tekijät: Salo V, Torma I
Toimittaja: Teijiro Isokawa,Katsunobu Imai,Nobuyuki Matsui,Ferdinand Peper,Hiroshi Umeo
Kustantaja: Sprinder-Verlag New York, MS Ingrid Cunningham, 175 Fifth Ave, New York, NY 10010 USA
Julkaisuvuosi: 2015
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Cellular automata and discrete complex systems
Tietokannassa oleva lehden nimi: CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS (AUTOMATA 2014)
Lehden akronyymi: Lect Notes Computer Sc
Sarjan nimi: Lecture notes in computer science
Vuosikerta: 8996
Aloitussivu: 135
Lopetussivu: 148
Sivujen määrä: 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.
