Deterministic ordered restarting automata for picture languages

被引：0
作者：
Friedrich Otto
František Mráz
机构：
[1] Universität Kassel,Fachbereich Elektrotechnik/Informatik
[2] Charles University,Faculty of Mathematics and Physics, Department of Computer Science
来源：
Acta Informatica | 2015年 / 52卷
关键词：
68 Q 45;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：30
相关论文
共 24 条
[1]  
Anselmo A(2009)A computational model for tiling recognizable two-dimensional languages Theor. Comput. Sci. 410 3520-3529
[2]  
Giammarresi D(2010)Deterministic and unambiguous families within recognizable two-dimensional languages Fundam. Inform. 98 143-166
[3]  
Madonia M(1992)Recognizable picture languages Int. J. Pattern Recognit. Artif. Intell. 6 241-256
[4]  
Anselmo A(1965)One-tape, off-line Turing machine computations Inf. Control 8 553-578
[5]  
Giammarresi D(1977)Some properties of two-dimensional on-line tessellation acceptors Inf. Sci. 13 95-121
[6]  
Madonia M(1998)Complexity of two-dimensional patterns J. Stat. Phys. 91 909-951
[7]  
Giammarresi D(2011)Church–Rosser picture languages and their applications in picture recognition J. Autom. Lang. Comb. 16 165-194
[8]  
Restivo A(2014)Two-dimensional Sgraffito automata RAIRO Theor. Inform. Appl. 48 505-539
[9]  
Hennie F(2013)Restarting tiling automata Int. J. Found. Comput. Sci. 24 863-878
[10]  
Inoue K(1972)Abstract families of matrices and picture languages Comput. Graph. Image Process. 1 284-307
123