Article contents
Polynomial languages with finite antidictionaries
Published online by Cambridge University Press: 22 November 2008
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.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2008
References
- 1
- Cited by