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

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.
2nd International Conference on Algebraic Informatics, CAI 2007
Thessaloniki, GREECE
MAY 21-25, 2007
Rilevanza internazionale
su invito
Settore INF/01 - Informatica
English
automata and formal languages; two-dimensional languages; tiling systems; unambiguity; determinism
Intervento a convegno
Giammarresi, D. (2007). Tiling recognizable two-dimensional languages. In ALGEBRAIC INFORMATICS (pp.75-86). BERLIN : SPRINGER-VERLAG BERLIN.
Giammarresi, D
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/35232
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact