A computational model for tiling recognizable two-dimensional languages

被引：20

作者：

Anselmo, Marcella ^{[2
]}

Giammarresi, Dora ^{[1
]}

Madonia, Maria ^{[3
]}

机构：

[1] Univ Roma Tor Vergata, Dipartimento Matemat, I-00133 Rome, Italy

[2] Univ Salerno, Dipartimento Informat & Applicaz, I-84084 Fisciano, SA, Italy

[3] Univ Catania, Dipartimento Matemat & Informat, I-95125 Catania, Italy

来源：

THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 37期

关键词：

Two-dimensional languages; Finite automata; Determinism; AUTOMATA;

D O I：

10.1016/j.tcs.2009.03.016

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Tiling systems are a well accepted model to define recognizable two-dimensional languages but they are not an effective device for recognition unless a scanning strategy for the pictures is fixed. We define a tiling automaton as a tiling system equipped with a scanning strategy and a suitable data structure. The class of languages accepted by tiling automata coincides with the REC family. In this framework it is possible to define determinism, non-determinism and unambiguity. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for two-dimensional languages. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：3520 / 3529

页数：10

共 17 条

[1]

Anselmo M, 2006, LECT NOTES COMPUT SC, V3845, P43

[2]

Anselmo M, 2007, LECT NOTES COMPUT SC, V4783, P290

[3]

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

[4] Unambiguous recognizable two-dimensional languages [J].

Anselmo, Marcella ;

Giammarresi, Dora ;

Madonia, Maria ;

Restivo, Antonio .

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2006, 40 (02) :277-293

[5]

Blum M., 1967, 8 ANN S SWITCH AUT T, P155

[6]

Eilenberg S., 1974, Automata, Languages, and Machines, VA

[7]

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

[8]

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

[9]

GIAMMARRESI D, 2007, TEXTS LOGIC GAMES, V2, P315

[10] NOTE ON 2-DIMENSIONAL FINITE AUTOMATA [J].

INOUE, K ;

TAKANAMI, I ;

NAKAMURA, A .

INFORMATION PROCESSING LETTERS, 1978, 7 (01) :49-52

← 1 2 →