Concatenation operations and restricted variants of two-dimensional automata

DOI10.1007/978-3-030-67731-2_11MaRDI QIDQ831799zbMATHOpenAlexFDO

Authors Taylor J. Smith, Kai Salomaa

Publication date 24 March 2022

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

zbMATH Keywords

concatenationclosure propertiestwo-way automatathree-way automatatwo-dimensional automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: A two-dimensional automaton operates on arrays of symbols. While a standard (four-way) two-dimensional automaton can move its input head in four directions, restricted two-dimensional automata are only permitted to move their input heads in three or two directions; these models are called three-way and two-way two-dimensional automata, respectively. In two dimensions, we may extend the notion of concatenation in multiple ways, depending on the words to be concatenated. We may row-concatenate (resp., column-concatenate) a pair of two-dimensional words when they have the same number of columns (resp., rows). In addition, the diagonal concatenation operation combines two words at their lower-right and upper-left corners, and is not dimension-dependent. In this paper, we investigate closure properties of restricted models of two-dimensional automata under various concatenation operations. We give non-closure results for two-way two-dimensional automata under row and column concatenation in both the deterministic and nondeterministic cases. We further give positive closure results for the same concatenation operations on unary nondeterministic two-way two-dimensional automata. Finally, we study closure properties of diagonal concatenation on both two- and three-way two-dimensional automata.

Recommendations

• Concatenation of inputs in a two-way automaton
• The complexity of concatenation on deterministic and alternating finite automata
• Concatenation of regular languages and descriptional complexity
• Concatenation of Regular Languages and Descriptional Complexity
• Degrees of restriction for two-dimensional automata
• Decision problems for restricted variants of two-dimensional automata
• Some remarks on two-dimensional finite automata
• scientific article; zbMATH DE number 1452989
• Some results concerning two-dimensional turing machines and finite automata
• Operations on Boolean and alternating finite automata

Cites work

• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• A note on two-dimensional finite automata
• A survey of two-dimensional automata theory
• A survey on picture-walking automata
• Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines
• Mathematical Foundations of Computer Science 2005
• New operations and regular expressions for two-dimensional languages over one-letter alphabet

Cited in

(4)

• scientific article; zbMATH DE number 7770057 (Why is no real title available?)
• The complexity of concatenation on deterministic and alternating finite automata
• 2D oxide picture languages and their properties
• Concatenation of inputs in a two-way automaton

This page was built for publication: Concatenation operations and 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 Q831799)