Minimal forbidden words

 Maxime Crochemore
Université de Marne-la-Vallée, mai 1998
M. Crochemore, F. Mignosi and A. Restivo, Automata and forbidden words, Information Processing Letters, 67,3 (1998) 111-117.
In dvi or ps format, 11pp.

Abstract

Let L(M) be the (factorial) language avoiding a given anti-factorial language M. We design an automaton accepting L(M) and built from the language M. The construction is effective 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.

Keywords: factorial language, anti-factorial language, factor code, factor automaton, forbidden word, avoiding a word, failure function.

Contents

  1. Introduction
  2. Avoiding an anti-factorial language
  3. Factor automaton of a single word
  4. Minimal forbidden words of a word
 

Related references

Preliminary version in:
M. Crochemore, F. Mignosi and A. Restivo. Minimal Forbidden Words and Factor Automata. in ( MFCS'98, L. Brim, J. Gruska, J. Zlatuska, eds., LNCS 1450, Springer, 1998) 665-673.
In dvi or ps format, 9pp.
M. Crochemore, F. Mignosi, A. Restivo, S. Salemi, Data Compression using Antidictionaries, Technical Report, IGM-98-10, Institut Gaspard-Monge, 1998, 20 pages.
In dvi or ps format, 20pp.
M.-P. Béal, F. Mignosi and A. Restivo. Minimal Forbidden Words and Symbolic Dynamics. in ( STACS'96, C. Puech and R. Reischuk, eds., LNCS 1046, Springer, 1996) 555--566.
In ps format, 12pp.
Institut Gaspard-Monge, Laboratoire d'informatique, le 6 octobre 1999, Maxime Crochemore