Two-dimensional languages can be recognized by tiling systems. A tiling system becomes an effective device for recognition when a scanning strategy on pictures is fixed. We define a Tiling Automaton as a tiling system together with a scanning strategy and a suitable data structure. In this framework it is possible to define determinism, non-determinism and unambiguity. The class of languages accepted by tiling automata coincides with REC family. Tiling automata are able to simulate on-line tessellation automata. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for recognition of two-dimensional languages. © Springer-Verlag Berlin Heidelberg 2007.
Anselmo, M., Giammarresi, D., Madonia, M. (2007). Tiling automaton: A computational model for recognizable two-dimensional languages. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.290-302). SPRINGER-VERLAG BERLIN.
Tiling automaton: A computational model for recognizable two-dimensional languages
GIAMMARRESI, DORA;
2007-01-01
Abstract
Two-dimensional languages can be recognized by tiling systems. A tiling system becomes an effective device for recognition when a scanning strategy on pictures is fixed. We define a Tiling Automaton as a tiling system together with a scanning strategy and a suitable data structure. In this framework it is possible to define determinism, non-determinism and unambiguity. The class of languages accepted by tiling automata coincides with REC family. Tiling automata are able to simulate on-line tessellation automata. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for recognition of two-dimensional languages. © Springer-Verlag Berlin Heidelberg 2007.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
