Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-19T12:36:07.265Z Has data issue: false hasContentIssue false
  • English
  • Français

Polynomial languages with finite antidictionaries

Published online by Cambridge University Press:  22 November 2008

Arseny M. Shur
Arseny M. Shur*
Affiliation:
Ural State University, Ekaterinburg, Russia; [email protected]
Get access

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.

Keywords

Regular languagefinite antidictionarycombinatorial complexitywed-like automaton
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 2 , April 2009 , pp. 269 - 279
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Brandenburg, F.-J., Uniformly growing k-th power free homomorphisms. Theoret. Comput. Sci. 23 (1983) 69–82. CrossRef
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.
Crochemore, M., Mignosi, F. and Restivo, A., Automata and forbidden words. Inform. Process. Lett. 67 (1998) 111–117. CrossRef
Ehrenfeucht, A. and Rozenberg, G., On subword complexities of homomorphic images of languages. RAIRO-Theor. Inf. Appl. 16 (1982) 303–316.
Kobayashi, Y., Repetition-free words. Theoret. Comput. Sci. 44 (1986) 175–197. CrossRef
A.M. Shur, Combinatorial complexity of rational languages. Discr. Anal. Oper. Res., Ser. 1 12 (2005) 78–99 (in Russian).