Polynomial languages with finite antidictionaries
RAIRO - Theoretical Informatics and Applications (2008)
- Volume: 43, Issue: 2, page 269-279
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topShur, Arseny M.. "Polynomial languages with finite antidictionaries." RAIRO - Theoretical Informatics and Applications 43.2 (2008): 269-279. <http://eudml.org/doc/92916>.
@article{Shur2008,
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},
keywords = {Regular language; finite antidictionary; combinatorial complexity; wed-like automaton; regular language},
language = {eng},
month = {11},
number = {2},
pages = {269-279},
publisher = {EDP Sciences},
title = {Polynomial languages with finite antidictionaries},
url = {http://eudml.org/doc/92916},
volume = {43},
year = {2008},
}
TY - JOUR
AU - Shur, Arseny M.
TI - Polynomial languages with finite antidictionaries
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/11//
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; regular language
UR - http://eudml.org/doc/92916
ER -
References
top- F.-J. Brandenburg, Uniformly growing k-th power free homomorphisms. Theoret. Comput. Sci.23 (1983) 69–82.
- 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.
- M. Crochemore, F. Mignosi and A. Restivo, Automata and forbidden words. Inform. Process. Lett.67 (1998) 111–117.
- A. Ehrenfeucht and G. Rozenberg, On subword complexities of homomorphic images of languages. RAIRO-Theor. Inf. Appl.16 (1982) 303–316.
- Y. Kobayashi, Repetition-free words. Theoret. Comput. Sci.44 (1986) 175–197.
- A.M. Shur, Combinatorial complexity of rational languages. Discr. Anal. Oper. Res., Ser. 112 (2005) 78–99 (in Russian).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.