Minimal forbidden words and factor automata

Maxime Crochemore (1) , Filippo Mignosi (2) , Antonio Restivo (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 DICGIM - Dipartimento di Ingegneria Chimica, Gestionale, Informatica, Meccanica [Palermo]

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.

Mots clés: factorial language; anti-factorial language; factor code; factor automaton; forbidden word; avoiding a word; failure function

Domaines: Algorithme et structure de données [cs.DS]

Maxime Crochemore, Filippo Mignosi, Antonio Restivo. Minimal forbidden words and factor automata. Mathematical Foundations of Computer Science (Brno, 1998), 1998, France. pp.665-673. ⟨hal-00619990⟩