Geodesic
Classes of two-dimensional languages and recognizability conditions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 4, pp. 471-488

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

The paper deals with some classes of two-dimensional recognizable languages of “high complexity”, in a sense specified in the paper and motivated by some necessary conditions holding for recognizable and unambiguous languages. For such classes we can solve some open questions related to unambiguity, finite ambiguity and complementation. Then we reformulate a necessary condition for recognizability stated by Matz, introducing a new complexity function. We solve an open question proposed by Matz, showing that all the known necessary conditions for recognizability of a language and its complement are not sufficient. The proof relies on a family of languages defined by functions.

DOI : 10.1051/ita/2011003
Classification : 68Q45, 68Q70
Keywords: two-dimensional languages, unambiguity, complement 
@article{ITA_2010__44_4_471_0,
     author = {Anselmo, Marcella and Madonia, Maria},
     title = {Classes of two-dimensional languages and recognizability conditions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {471--488},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {4},
     year = {2010},
     doi = {10.1051/ita/2011003},
     mrnumber = {2775407},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011003/}
}
TY  - JOUR
AU  - Anselmo, Marcella
AU  - Madonia, Maria
TI  - Classes of two-dimensional languages and recognizability conditions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 471
EP  - 488
VL  - 44
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011003/
DO  - 10.1051/ita/2011003
LA  - en
ID  - ITA_2010__44_4_471_0
ER  - 
%0 Journal Article
%A Anselmo, Marcella
%A Madonia, Maria
%T Classes of two-dimensional languages and recognizability conditions
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 471-488
%V 44
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011003/
%R 10.1051/ita/2011003
%G en
%F ITA_2010__44_4_471_0
Anselmo, Marcella; Madonia, Maria. Classes of two-dimensional languages and recognizability conditions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 4, pp. 471-488. doi: 10.1051/ita/2011003

Cité par Sources :