Polynomial languages with finite antidictionaries
Arseny M. Shur · RAIRO - Theoretical Informatics and Applications · 2008
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.