Tiling systems that recognize two-dimensional languages are intrinsically non-deterministic models. We introduce the notion of deterministic tiling system that generalizes deterministic automata for strings. The corresponding family of languages matches all the requirements of a robust deterministic class. Furthermore we show that, differently from the one-dimensional case, there exist many classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties. © Springer-Verlag Berlin Heidelberg 2007.
Anselmo, M., Giammarresi, D., Madonia, M. (2007). From determinism to non-determinism in recognizable two-dimensional languages. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.36-47). SPRINGER-VERLAG BERLIN.
From determinism to non-determinism in recognizable two-dimensional languages
GIAMMARRESI, DORA;
2007-01-01
Abstract
Tiling systems that recognize two-dimensional languages are intrinsically non-deterministic models. We introduce the notion of deterministic tiling system that generalizes deterministic automata for strings. The corresponding family of languages matches all the requirements of a robust deterministic class. Furthermore we show that, differently from the one-dimensional case, there exist many classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties. © Springer-Verlag Berlin Heidelberg 2007.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
