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 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.
|Titolo:||A Computational Model for Tiling Recognizable Two-dimensional Languages|
|Autori interni:||MADONIA, Maria Serafina|
|Data di pubblicazione:||2009|
|Rivista:||THEORETICAL COMPUTER SCIENCE|
|Appare nelle tipologie:||1.1 Articolo in rivista|