Subshifts defined by nondeterministic and alternating plane-walking automata

Benjamin Hellouin de Menibus, Pacôme Perrotin

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-dime…