Abstract: In this article, we study classes of multidimensional subshifts 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.
Recommendations
Cites work
- A note on simple programs with two variables
- A sufficient condition for non-soficness of higher-dimensional subshifts
- A survey of two-dimensional automata theory
- A survey on picture-walking automata
- Classification of sofic projective subdynamics of multidimensional shifts of finite type
- Commutators of bipermutive and affine cellular automata
- Expressive Power of Pebble Automata
- Marker automata
- Multi-head finite automata: characterizations, concepts and open problems
- Tree-Walking Automata
- Tree-Walking Automata Do Not Recognize All Regular Languages
Cited in
(6)- Automata on the plane vs particles and collisions
- The group of reversible Turing machines
- Subshifts with sparse traces
- Multidimensional shifts of finite type and sofic shifts
- The group of reversible Turing machines: subgroups, generators, and computability
- Subshifts defined by nondeterministic and alternating plane-walking automata
This page was built for publication: Plane-walking automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501619)
