POLYNOMIAL LANGUAGES WITH FINITE ANTIDICTIONARIES
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.
finite antidictionary regular language combinatorial complexity wed-like automaton