LANGUAGES WITH A FINITE ANTIDICTIONARY: SOME GROWTH QUESTIONS

摘要

We study FAD-languages, which are regular languages defined by finite sets of forbidden factors, together with their "canonical" recognizing automata. we are mainly interested in the possible asymptotic orders of growth for such languages. We analyze certain simplifications of sets of forbidden factors and show that they "almost" preserve the canonical automata. Using this result and structural properties of canonical automata, we describe an algorithm that effectively lists all canonical automata having a sink strong component isomorphic to a given digraph, or report:, that no such automata exist. This algorithm can be used, in particular, to prove the existence of a FAD-language over a given alphabet with a given exponential growth rate. On the other hand, we give an example showing that the algorithm cannot prove non-existence of a FAD-language having a given growth rate. Finally, we provide some examples of canonical automata with a nontrivial condensation graph and of FAD-languages with a "complex" order of growth.