2026-07-20T06:35:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22854 2025-10-02T13:36:07Z ddc:004 open_access

Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata Hellouin de Menibus, Benjamin Perrotin, Pacôme Formal languages Finite automata Subshifts Symbolic dynamics Tilings Plane-walking automata were introduced by Salo & Törma to recognise languages of two-dimensional infinite words (subshifts), the counterpart of 4-way finite automata for two-dimensional finite words. We extend the model to allow for nondeterminism and alternation of quantifiers. We prove that the recognised subshifts form a strict subclass of sofic subshifts, and that the classes corresponding to existential and universal nondeterminism are incomparable and both larger that the deterministic class. We define a hierarchy of subshifts recognised by plane-walking automata with alternating quantifiers, which we conjecture to be strict. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Hellouin de Menibus and Pacôme Perrotin 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.48 urn:nbn:de:0030-drops-228540 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.48 eng https://creativecommons.org/licenses/by/4.0/legalcode