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

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.
11th International Conference on Developments in Language Theory, DLT 2007
Turku
3 July 2007 through 6 July 2007
The Academy of Finland;The Finnish Cultural Foundation;Finnish Academy of Science and Letters;Nokia Foundation;Turku University Foundation
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
English
Automata and formal languages; Two-dimensional languages; Unambiguity, determinism
Intervento a convegno
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.
Anselmo, M; Giammarresi, D; Madonia, M
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/35231
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 33
  • ???jsp.display-item.citation.isi??? 26
social impact