论文标题
二维自动机的串联操作和限制变体
Concatenation Operations and Restricted Variants of Two-Dimensional Automata
论文作者
论文摘要
二维自动机在符号阵列上运行。虽然标准（四方）二维自动机可以在四个方向上移动其输入头，但仅允许受限制的二维自动机将其输入头移动到三个或两个方向；这些模型分别称为三向和二维自动机。 在两个维度上，我们可以通过多种方式扩展串联的概念，具体取决于要串联的单词。当它们具有相同数量的列（分别，行）时，我们可能会划分陈述（分别为contar-concatenate）一对二维单词。此外，对角线串联操作在其右下和左上角结合了两个单词，并且不依赖尺寸。 在本文中，我们研究了各种串联操作下二维自动机的受限模型的闭合性能。在确定性和非确定性案例中，我们在行和列串联下的双向二维自动机给出了非关闭结果。我们进一步给出了对一级非确定二维二维自动机的相同串联操作的积极闭合结果。最后，我们研究了对角串联在两维自动机上的闭合性能。
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.
