Geodesic
Polynomial languages with finite antidictionaries
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 269-279

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

MR Zbl

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

DOI : 10.1051/ita:2008028
Classification : 68Q45, 68R15
Keywords: regular language, finite antidictionary, combinatorial complexity, wed-like automaton 
Shur, Arseny M. Polynomial languages with finite antidictionaries. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 269-279. doi: 10.1051/ita:2008028
@article{ITA_2009__43_2_269_0,
     author = {Shur, Arseny M.},
     title = {Polynomial languages with finite antidictionaries},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {269--279},
     year = {2009},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {2},
     doi = {10.1051/ita:2008028},
     mrnumber = {2512259},
     zbl = {1166.68026},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2008028/}
}
TY  - JOUR
AU  - Shur, Arseny M.
TI  - Polynomial languages with finite antidictionaries
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 269
EP  - 279
VL  - 43
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2008028/
DO  - 10.1051/ita:2008028
LA  - en
ID  - ITA_2009__43_2_269_0
ER  - 
%0 Journal Article
%A Shur, Arseny M.
%T Polynomial languages with finite antidictionaries
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 269-279
%V 43
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2008028/
%R 10.1051/ita:2008028
%G en
%F ITA_2009__43_2_269_0

Cité par Sources :