2019/04/24 by Taylor J. Smith, Smith, Taylor J., Kai Salomaa +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #20F10 (secondary) #68Q45 (primary) #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #cs.FL #msc:20F10 #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1904.11100
arxiv created 2019/04/24 · openalex publication_date 2019/04/24 · arxiv updated 2019/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A two-dimensional finite automaton has a read-only input head that moves in four directions on a finite array of cells labelled by symbols of the input alphabet. A three-way two-dimensional automaton is prohibited from making upward moves, while a two-way two-dimensional automaton can only move downward and rightward. We show that the language emptiness problem for unary three-way nondeterministic two-dimensional automata is NP-complete, and is in P for general-alphabet two-way nondeterministic two-dimensional automata. We show that the language equivalence problem for two-way deterministic two-dimensional automata is decidable, while both the equivalence and universality problems for two-way nondeterministic two-dimensional automata are undecidable. The deterministic case is the first known positive decidability result for the equivalence problem on two-dimensional automata over a general alphabet. We show that there exists a unary three-way deterministic two-dimensional automaton with a nonregular column projection, and we show that the row projection of a unary three-way nondeterministic two-dimensional automaton is always regular.