Concatenation operations and restricted variants of two-dimensional automata

DOI10.1007/978-3-030-67731-2_11zbMATH Open1490.68130arXiv2008.11164OpenAlexW3126348830MaRDI QIDQ831799FDOQ831799

Taylor J. Smith, Kai Salomaa

Publication date: 24 March 2022

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.

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)

Cites Work

• Title not available (Why is that?)
• A Survey on Picture-Walking Automata
• Mathematical Foundations of Computer Science 2005
• A note on two-dimensional finite automata
• Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines
• New operations and regular expressions for two-dimensional languages over one-letter alphabet
• A survey of two-dimensional automata theory

Cited In (3)

• The complexity of concatenation on deterministic and alternating finite automata
• Title not available (Why is that?)
• 2D oxide picture languages and their properties

Recommendations

• Title not available (Why is that?) 👍 👎
• Concatenation of regular languages and descriptional complexity 👍 👎
• Concatenation of inputs in a two-way automaton 👍 👎
• The complexity of concatenation on deterministic and alternating finite automata 👍 👎
• Some remarks on two-dimensional finite automata 👍 👎
• Operations on Boolean and alternating finite automata 👍 👎
• Degrees of restriction for two-dimensional automata 👍 👎
• Decision problems for restricted variants of two-dimensional automata 👍 👎
• Concatenation of Regular Languages and Descriptional Complexity 👍 👎
• Some results concerning two-dimensional turing machines and finite automata 👍 👎

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)