Skip to Main content Skip to Navigation
Conference papers

Minimal forbidden words and factor automata

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619990
Contributor : Maxime Crochemore <>
Submitted on : Tuesday, March 26, 2013 - 11:07:42 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Document(s) archivé(s) le : Thursday, June 27, 2013 - 2:40:12 AM

File

minimal_forbidden_words_and_fa...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619990, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

288

Files downloads

264