Deterministic ordered restarting automata for picture languages

被引：10

作者：

Otto, Friedrich ^{[1
]}

Mraz, Frantisek ^{[2
]}

机构：

[1] Univ Kassel, Fachbereich Elektrotech Informat, D-34109 Kassel, Germany

[2] Charles Univ Prague, Fac Math & Phys, Dept Comp Sci, Prague 11800 1, Czech Republic

来源：

ACTA INFORMATICA | 2015年 / 52卷 / 7-8期

关键词：

68; Q; 45;

D O I：

10.1007/s00236-015-0230-5

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The ordered restarting automaton (processing strings) is introduced, and it is shown that its nondeterministic variant is very expressive, as it accepts some languages that are not even context-free, while the deterministic ordered restarting automata just accept the regular languages. Then three different extensions of the deterministic ordered restarting automaton to two-dimensional inputs are defined that differ in the way in which they can move their read/write windows. We compare the classes of picture languages that these types of automata accept to each other and to some well studied classes of picture languages from the literature, and we present some closure and non-closure properties for them.

引用

页码：593 / 623

页数：31

共 29 条

[1]

Anselmo M, 2007, LECT NOTES COMPUT SC, V4588, P36

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

Anselmo, Marcella ;

Giammarresi, Dora ;

Madonia, Maria .

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

[3] A computational model for tiling recognizable two-dimensional languages [J].

Anselmo, Marcella ;

Giammarresi, Dora ;

Madonia, Maria .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (37) :3520-3529

[4]

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

[5]

Borchert B., 2007, LATA 2007, P175

[6]

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

[7]

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

[8] ONE-TAPE OFF-LINE TURING MACHINE COMPUTATIONS [J].

HENNIE, FC .

INFORMATION AND CONTROL, 1965, 8 (06) :553-&

[9] SOME PROPERTIES OF 2-DIMENSIONAL ONLINE TESSELATION ACCEPTORS [J].

INOUE, K ;

NAKAMURA, A .

INFORMATION SCIENCES, 1977, 13 (02) :95-121

[10]

JANCAR P, 1992, LECT NOTES COMPUT SC, V629, P307

← 1 2 3 →