Tiling recognizable two-dimensional languages, also known as REC, generalize recognizable string languages to two dimensions and share with them several theoretical properties. Nevertheless family REC is not closed under complementation and this implies that it is intrinsically non-deterministic. We consider different notions of unambiguity and determinism and the corresponding REC subclasses: they define a hierarchy inside REC. We show that some definitions of unambiguity are equivalent to particular notions of determinism and therefore the corresponding classes have linear parsing algorithms and are closed under complementation.

Giammarresi, D. (2011). Exploring inside Tiling Recognizable Picture Languages to Find Deterministic subclasses. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 22(7), 1519-1532 [10.1142/S0129054111008854].

Exploring inside Tiling Recognizable Picture Languages to Find Deterministic subclasses

GIAMMARRESI, DORA
2011-11-01

Abstract

Tiling recognizable two-dimensional languages, also known as REC, generalize recognizable string languages to two dimensions and share with them several theoretical properties. Nevertheless family REC is not closed under complementation and this implies that it is intrinsically non-deterministic. We consider different notions of unambiguity and determinism and the corresponding REC subclasses: they define a hierarchy inside REC. We show that some definitions of unambiguity are equivalent to particular notions of determinism and therefore the corresponding classes have linear parsing algorithms and are closed under complementation.
nov-2011
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Con Impact Factor ISI
Two-dimensional languages; tiling systems; determinism
Giammarresi, D. (2011). Exploring inside Tiling Recognizable Picture Languages to Find Deterministic subclasses. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 22(7), 1519-1532 [10.1142/S0129054111008854].
Giammarresi, D
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
dlt10-specissue.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Licenza: Copyright dell'editore
Dimensione 132.07 kB
Formato Adobe PDF
132.07 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: https://hdl.handle.net/2108/101608
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact