Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata.
作者： Kai Salomaa , Taylor J. Smith
DOI:
关键词: Column (database) 、 Discrete mathematics 、 Nondeterministic algorithm 、 Unary operation 、 Concatenation 、 Automaton 、 Projection (mathematics) 、 Row 、 Computer science 、 Word (computer architecture)
摘要: The row projection (resp., column projection) of a two-dimensional language $L$ is the one-dimensional consisting all first rows columns) each word in $L$. operation has previously been studied under name "frontier language", and previous work focused on one- classes. In this paper, we study projections languages recognized by various automaton We show that both (four-way) automata are exactly context-sensitive. also unary three-way can be using nondeterministic logspace. Finally, state complexity for two-way automata, focusing operations union diagonal concatenation.
参考文章(20)
Marcella Anselmo, Dora Giammarresi, Maria Madonia, Classification of String Languages via Tiling Recognizable Picture Languages Language and Automata Theory and Applications. ,vol. 6638, pp. 105- 116 ,(2011) , 10.1007/978-3-642-21254-3_7
悦朗 守屋, J.E.Hopcroft, J.D. Ullman 著, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, A5変形版, X+418, \6,670, 1979 情報処理. ,vol. 21, pp. 802- 803 ,(1980)
Jarkko Kari, Cristopher Moore, Rectangles and Squares Recognized by Two-Dimensional Automata Theory Is Forever. pp. 134- 144 ,(2004) , 10.1007/978-3-540-27812-2_13
Two‐Dimensional Automata John Wiley & Sons, Inc.. pp. 89- 122 ,(2011) , 10.1002/9781118032381.CH4
Dora Giammarresi, Antonio Restivo, Two-dimensional languages Handbook of formal languages, vol. 3. pp. 215- 267 ,(1997) , 10.1007/978-3-642-59126-6_4
Arto Salomaa, Ian N. Sneddon, Theory of automata ,(1969)
J. C. Shepherdson, The reduction of two-way automata to one-way automata Ibm Journal of Research and Development. ,vol. 3, pp. 198- 200 ,(1959) , 10.1147/RD.32.0198
S.-Y. Kuroda, Classes of languages and linear-bounded automata Information and Control. ,vol. 7, pp. 207- 223 ,(1964) , 10.1016/S0019-9958(64)90120-2
M. Latteux, D. Simplot, Context-sensitive string languages and recognizable picture languages Information & Computation. ,vol. 138, pp. 160- 169 ,(1997) , 10.1006/INCO.1997.2659
MARKUS HOLZER, MARTIN KUTRIB, NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES International Journal of Foundations of Computer Science. ,vol. 14, pp. 1087- 1102 ,(2003) , 10.1142/S0129054103002199