Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata

被引：1

作者：

Smith, Taylor J. ^{[1
]}

Salomaa, Kai ^{[1
]}

机构：

[1] Queens Univ, Sch Comp, Kingston, ON K7L 2N8, Canada

来源：

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2020 | 2020年 / 12442卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Language classes; Projection languages; Space complexity; Three-way automata; Two-dimensional automata; Two-way automata;

D O I：

10.1007/978-3-030-62536-8_17

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The row projection (resp., column projection) of a given two-dimensional language L is the one-dimensional language consisting of first rows (resp., first columns) of all two-dimensional words in L. The operation of row projection has previously been studied under the name "frontier language" , and previous work in this area has focused primarily 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.

引用

页码：206 / 218

页数：13

共 22 条

[1]

[Anonymous], 1979, Picture Languages-Formal Models of Picture Recognition

[2]

Anselmo M, 2011, LECT NOTES COMPUT SC, V6638, P105, DOI 10.1007/978-3-642-21254-3_7

[3] Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages [J].

Anselmo, Marcella ;

Giammarresi, Dora ;

Madonia, Maria .

FUNDAMENTA INFORMATICAE, 2010, 98 (2-3) :143-166

[4]

Blum Manuel., 1967, 8th Annual Symposium on Switching and Automata Theory, Austin, Texas, USA, October 18-20, 1967, P155

[5]

Giammarresi D., 1992, International Journal of Pattern Recognition and Artificial Intelligence, V6, P241, DOI 10.1142/S021800149200014X

[6]

Giammarresi D., 1997, HDB FORMAL LANGUAGES, V3, P215, DOI DOI 10.1007/978-3-642-59126-6_4

[7] ON RECOGNITION OF PRIMES BY AUTOMATA [J].

HARTMANIS, J ;

SHANK, H .

JOURNAL OF THE ACM, 1968, 15 (03) :382-+

[8]

Holzer M., 2003, International Journal of Foundations of Computer Science, V14, P1087, DOI 10.1142/S0129054103002199

[9]

Hopcroft J. E., 1979, Introduction to Automata Theory, Languages, and Computation

[10]

INOUE K, 1992, LECT NOTES COMPUT SC, V654, P133

← 1 2 3 →