6533b7cffe1ef96bd1259abf
RESEARCH PRODUCT
Automata and forbidden words
Antonio RestivoMaxime CrochemoreFilippo Mignosisubject
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Büchi automaton0102 computer and information sciences02 engineering and technologyω-automaton01 natural sciencesTheoretical Computer ScienceCombinatoricsDeterministic automaton0202 electrical engineering electronic engineering information engineeringTwo-way deterministic finite automatonNondeterministic finite automatonMathematicsPowerset constructionLevenshtein automaton020206 networking & telecommunicationsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nonlinear Sciences::Cellular Automata and Lattice GasesComputer Science ApplicationsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematicsSignal ProcessingProbabilistic automatonComputer Science::Programming LanguagesComputer Science::Formal Languages and Automata TheoryInformation Systemsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-08-01 |