论文标题
二维自动机的投影语言的识别和复杂性结果
Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata
论文作者
论文摘要
二维语言$ L $的行投影（分别，列投影）是由$ L $中每个二维单词的所有第一行（分别，第一列）组成的一维语言。先前以“ Frontier语言”的名称研究了行投影的操作，以前的工作集中在一维语言类上。 在本文中，我们研究了各种二维自动机班认可的语言的预测。我们表明，（四方）二维自动机识别的语言的行和列投影都是上下文敏感的。我们还表明，可以使用非确定的Logspace识别由一单向三维自动机识别的语言的列投影。最后，我们研究了双向二维自动机的投影语言的国家复杂性，重点是工会和对角线串联的语言运作。
The row projection (resp., column projection) of a two-dimensional language $L$ is the one-dimensional language consisting of all first rows (resp., first columns) of each two-dimensional word in $L$. The operation of row projection has previously been studied under the name "frontier language", and previous work has focused on one- and two-dimensional language classes. In this paper, we study projections of languages recognized by various two-dimensional automaton classes. We show that both the row and column projections of languages recognized by (four-way) two-dimensional automata are exactly context-sensitive. We also show that the column projections of languages recognized by unary three-way two-dimensional automata can be recognized using nondeterministic logspace. Finally, we study the state complexity of projection languages for two-way two-dimensional automata, focusing on the language operations of union and diagonal concatenation.
