Minimal forbidden words and factor automata
Résumé
Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is eff ective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.
Fichier principal
minimal_forbidden_words_and_factor_automata.pdf (266.23 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...