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.ÃÂ&nbsp;[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.

Fici, G., Restivo, A., Rizzo, L. (2017). Minimal forbidden factors of circular words. In S. Brlek, F. Dolce, C. Reutenauer, E. Vandomme (a cura di), Combinatorics on Words, 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11-15, 2017, Proceedings (pp. 36-48). Springer Verlag [10.1007/978-3-319-66396-8_5].

Minimal forbidden factors of circular words

Abstract

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.
Scheda breve Scheda completa Scheda completa (DC)
2017
Settore INF/01 - Informatica
Fici, G., Restivo, A., Rizzo, L. (2017). Minimal forbidden factors of circular words. In S. Brlek, F. Dolce, C. Reutenauer, E. Vandomme (a cura di), Combinatorics on Words, 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11-15, 2017, Proceedings (pp. 36-48). Springer Verlag [10.1007/978-3-319-66396-8_5].
File in questo prodotto:
File
Minimal Forbidden Factors of Circular Words.pdf

Solo gestori archvio

Dimensione 400.22 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10447/248542`