Plane-walking automata

DOI10.1007/978-3-319-18812-6_11MaRDI QIDQ5501619zbMATH OpenOpenAlexFDO

Authors Ville Salo, Ilkka A. Törmä

Publication date 4 August 2015

Published in Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.6701

zbMATH Keywords

multihead automatonplane-walking automatonsubshift

Mathematics Subject Classification ID

Multidimensional shifts of finite type (37B51) Formal languages and automata (68Q45)

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

• On three-way two-dimensional multicounter automata
• Subshifts, MSO logic, and collapsing hierarchies
• Multi-head finite automata: characterizations, concepts and open problems
• Finite state automata representing two-dimensional subshifts
• Low complexity classes of multidimensional cellular automata

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)