6533b86efe1ef96bd12cc804

RESEARCH PRODUCT

Minimal Forbidden Factors of Circular Words

Antonio RestivoGabriele FiciLaura Rizzo

subject

L-automatonDiscrete mathematicsFactorialFibonacci numberSettore INF/01 - InformaticaComputer Science (all)Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)0102 computer and information sciences02 engineering and technologyCircular wordMinimal forbidden factor01 natural sciencesTheoretical Computer ScienceSet (abstract data type)010201 computation theory & mathematicsIf and only ifTrie0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingComputer Science::Formal Languages and Automata TheoryWord (computer architecture)Mathematics

description

Minimal forbidden factors are a useful tool for investigating properties of words and languages. Two factorial languages are distinct if and only if they have different (antifactorial) sets of minimal forbidden factors. There exist algorithms for computing the minimal forbidden factors of a word, as well as of a regular factorial language. Conversely, Crochemore et al. [IPL, 1998] gave an algorithm that, given the trie recognizing a finite antifactorial language M, computes a DFA of the language having M as set of minimal forbidden factors. In the same paper, they showed that the obtained DFA is minimal if the input trie recognizes the minimal forbidden factors of a single word. We generalize this result to the case of a circular word. We also discuss combinatorial properties of the minimal forbidden factors of a circular word. Finally, we characterize the minimal forbidden factors of the circular Fibonacci words.

yearjournalcountryeditionlanguage
2017-01-01
https://doi.org/10.1007/978-3-319-66396-8_5