# Polynomial languages with finite antidictionaries

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2009)

- Volume: 43, Issue: 2, page 269-279
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topShur, Arseny M.. "Polynomial languages with finite antidictionaries." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 43.2 (2009): 269-279. <http://eudml.org/doc/245795>.

@article{Shur2009,

abstract = {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.},

author = {Shur, Arseny M.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {regular language; finite antidictionary; combinatorial complexity; wed-like automaton},

language = {eng},

number = {2},

pages = {269-279},

publisher = {EDP-Sciences},

title = {Polynomial languages with finite antidictionaries},

url = {http://eudml.org/doc/245795},

volume = {43},

year = {2009},

}

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

PB - EDP-Sciences

VL - 43

IS - 2

SP - 269

EP - 279

AB - 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.

LA - eng

KW - regular language; finite antidictionary; combinatorial complexity; wed-like automaton

UR - http://eudml.org/doc/245795

ER -

## References

top- [1] F.-J. Brandenburg, Uniformly growing $k$-th power free homomorphisms. Theoret. Comput. Sci. 23 (1983) 69–82. Zbl0508.68051MR693069
- [2] C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of formal languages, Vol. 1, Chap. 6, edited by G. Rosenberg, A. Salomaa. Springer, Berlin (1997), 329–438. MR1469998
- [3] M. Crochemore, F. Mignosi and A. Restivo, Automata and forbidden words. Inform. Process. Lett. 67 (1998) 111–117. Zbl06590735MR1638178
- [4] A. Ehrenfeucht and G. Rozenberg, On subword complexities of homomorphic images of languages. RAIRO-Theor. Inf. Appl. 16 (1982) 303–316. Zbl0495.68069MR707633
- [5] Y. Kobayashi, Repetition-free words. Theoret. Comput. Sci. 44 (1986) 175–197. Zbl0596.20058MR860554
- [6] A.M. Shur, Combinatorial complexity of rational languages. Discr. Anal. Oper. Res., Ser. 1 12 (2005) 78–99 (in Russian). Zbl1249.68107MR2168157

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.