6533b7d6fe1ef96bd126720e

RESEARCH PRODUCT

Minimal forbidden words and factor automata

Maxime CrochemoreAntonio RestivoFilippo Mignosi

subject

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESfailure functionfactor code[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Büchi automatonComputerApplications_COMPUTERSINOTHERSYSTEMS[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciencesavoiding a wordω-automaton01 natural sciencesfactorial languageReversible cellular automatonCombinatoricsDeterministic automatonanti-factorial languageNondeterministic finite automaton0101 mathematicsMathematicsfactor automatonPowerset constructionLevenshtein automaton010102 general mathematicsforbidden wordComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)16. Peace & justiceNonlinear Sciences::Cellular Automata and Lattice GasesTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematicsProbabilistic automatonPhysics::Accelerator PhysicsComputer Science::Programming LanguagesHigh Energy Physics::ExperimentComputer Science::Formal Languages and Automata Theory

description

International audience; 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.

yearjournalcountryeditionlanguage
1998-01-01
https://hal.science/hal-00619990