Polynomial languages with finite antidictionaries
Ural State University, Ekaterinburg, Russia; Arseny.Shur@usu.ru
Accepted: 14 October 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.
Mathematics Subject Classification: 68Q45 / 68R15
Key words: Regular language / finite antidictionary / combinatorial complexity / wed-like automaton
© EDP Sciences, 2008