Automata and forbidden words - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Information Processing Letters Année : 1998

Automata and forbidden words

Résumé

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 ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.
Fichier principal
Vignette du fichier
9806-IPL.pdf (270.72 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619578 , version 1 (13-02-2013)

Identifiants

Citer

Maxime Crochemore, Filippo Mignosi, Antonio Restivo. Automata and forbidden words. Information Processing Letters, 1998, 67 (3), pp.111-117. ⟨10.1016/S0020-0190(98)00104-5⟩. ⟨hal-00619578⟩
222 Consultations
681 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More