A Computational Model for Tiling Recognizable Two-dimensional Languages

Tiling systems are a well accepted model to define recognizabletwo-dimensional languages but they are not an effective device forrecognition unless a "scanning strategy" for the pictures isfixed. We define a tiling automaton as a tiling systemequipped with a scanning strategy and a suitable data structure.The class of languages accepted by tiling automata coincides withREC family. In this framework it is possible to definedeterminism, non-determinism and unambiguity. Then (deterministic) tiling automata are compared with the other known(deterministic) automata models for two-dimensional languages.