Tiling recognizable two-dimensional languages generalizes recognizable string languages to two dimensions and share with them several properties. Nevertheless two-dimensional recognizable languages are not closed under complement and this implies that are intrinsically non-deterministic. We introduce the notion of deterministic and unambiguous tiling system that generalizes deterministic and unambiguous automata for strings and show that, differently from the one-dimensional case, there exist other distinct classes besides deterministic, unambiguous and non-deterministic families that can be separated by means of examples and decidability-properties. Finally we introduce a model of automaton, referred to as tiling automaton, defined as a scanning strategy plus a transition function given by a tiling system. Languages recognized. by tiling automata are compared with ones recognized by on-line tesselation automata and four-way automata.
Giammarresi, D. (2007). Tiling recognizable two-dimensional languages. In ALGEBRAIC INFORMATICS (pp.75-86). BERLIN : SPRINGER-VERLAG BERLIN.
Tiling recognizable two-dimensional languages
GIAMMARRESI, DORA
2007-01-01
Abstract
Tiling recognizable two-dimensional languages generalizes recognizable string languages to two dimensions and share with them several properties. Nevertheless two-dimensional recognizable languages are not closed under complement and this implies that are intrinsically non-deterministic. We introduce the notion of deterministic and unambiguous tiling system that generalizes deterministic and unambiguous automata for strings and show that, differently from the one-dimensional case, there exist other distinct classes besides deterministic, unambiguous and non-deterministic families that can be separated by means of examples and decidability-properties. Finally we introduce a model of automaton, referred to as tiling automaton, defined as a scanning strategy plus a transition function given by a tiling system. Languages recognized. by tiling automata are compared with ones recognized by on-line tesselation automata and four-way automata.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.