Decision problems for restricted variants of two-dimensional automata

DOI10.1007/978-3-030-23679-3_18MaRDI QIDQ2177610zbMATH OpenOpenAlexFDO

Authors Taylor J. Smith, Kai Salomaa

Publication date 6 May 2020

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

zbMATH Keywords

decision problemlanguage emptinesslanguage equivalencethree-way automatatwo-dimensional automatatwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: 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.

Recommendations

• Decision problems and projection languages for restricted variants of two-dimensional automata
• Some results concerning two-dimensional turing machines and finite automata
• Three-way automata on rectangular types over a one-letter alphabet
• Some remarks on two-dimensional finite automata
• Membership problem for two-dimensional general row jumping finite automata

Cited in

(10)

• Three-way automata on rectangular types over a one-letter alphabet
• Some remarks on two-dimensional finite automata
• Two-dimensional pattern matching against local and regular-like picture languages
• Decision problems and projection languages for restricted variants of two-dimensional automata
• Two-Dimensional Limited Context Restarting Automata
• Some results concerning two-dimensional turing machines and finite automata
• Developments in Language Theory
• Membership problem for two-dimensional general row jumping finite automata
• Two dimensional fuzzy regular languages
• Concatenation operations and restricted variants of two-dimensional automata

This page was built for publication: Decision problems for restricted variants of two-dimensional automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2177610)