Alternating hierarchy of sushifts defined by nondeterministic plane-walking automata
<|reference_start|>Alternating hierarchy of sushifts defined by nondeterministic plane-walking automata: Plane-walking automata were introduced by Salo & T\"orma 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.<|reference_end|>
@article{de menibus2024alternating,
    title={Alternating hierarchy of sushifts defined by nondeterministic
  plane-walking automata},
    author={Benjamin Hellouin de Menibus and Pac^ome Perrotin},
    journal={arXiv preprint arXiv:2409.08024},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.08024},
    primaryClass={cs.FL}
}