Automata and forbidden words

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 ν, 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619578
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 6:24:42 PM
Last modification on : Tuesday, October 30, 2018 - 5:04:09 PM
Long-term archiving on: Tuesday, May 14, 2013 - 2:50:09 AM

File

9806-IPL.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

399

Files downloads

450