Unambiguous recognizable two-dimensional languages

Antonio Restivo, Dora Giammarresi, Maria Madonia, Marcella Anselmo

Risultato della ricerca: Article

45 Citazioni (Scopus)

Abstract

We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure properties of UREC are presented. Finally we show that it is undecidable whether a given tiling system is unambiguous.
Lingua originaleEnglish
pagine (da-a)267-293
RivistaRAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS
Volume40
Stato di pubblicazionePublished - 2006

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Science Applications

Cita questo

Restivo, A., Giammarresi, D., Madonia, M., & Anselmo, M. (2006). Unambiguous recognizable two-dimensional languages. RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS, 40, 267-293.