Geodesic
Unambiguous recognizable two-dimensional languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 277-293

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita:2006008
Classification : 68Q45, 68Q10
Keywords: automata and formal languages, unambiguity, determinism, two-dimensional languages 
@article{ITA_2006__40_2_277_0,
     author = {Anselmo, Marcella and Giammarresi, Dora and Madonia, Maria and Restivo, Antonio},
     title = {Unambiguous recognizable two-dimensional languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {277--293},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {2},
     year = {2006},
     doi = {10.1051/ita:2006008},
     mrnumber = {2252639},
     zbl = {1112.68085},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2006008/}
}
TY  - JOUR
AU  - Anselmo, Marcella
AU  - Giammarresi, Dora
AU  - Madonia, Maria
AU  - Restivo, Antonio
TI  - Unambiguous recognizable two-dimensional languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 277
EP  - 293
VL  - 40
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2006008/
DO  - 10.1051/ita:2006008
LA  - en
ID  - ITA_2006__40_2_277_0
ER  - 
%0 Journal Article
%A Anselmo, Marcella
%A Giammarresi, Dora
%A Madonia, Maria
%A Restivo, Antonio
%T Unambiguous recognizable two-dimensional languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 277-293
%V 40
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2006008/
%R 10.1051/ita:2006008
%G en
%F ITA_2006__40_2_277_0
Anselmo, Marcella; Giammarresi, Dora; Madonia, Maria; Restivo, Antonio. Unambiguous recognizable two-dimensional languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 277-293. doi: 10.1051/ita:2006008

Cité par Sources :