Mignosi, F.; Restivo, A.; Sciortino, M. Words and forbidden factors. (English) Zbl 0997.68093 Theor. Comput. Sci. 273, No. 1-2, 99-117 (2002). Summary: Given a finite or infinite word \(v,\) we consider the set \(M(v)\) of minimal forbidden factors of \(v.\) We show that the set \(M(v)\) is of fundamental importance in determining the structure of the word \(v.\) In the case of a finite word \(w\) we consider two parameters that are related to the size of \(M(w):\) the first counts the minimal forbidden factors of \(w\) and the second gives the length of the longest minimal forbidden factor of \(w.\) We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word \(w.\) We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two problems: (i) given \(w,\) construct the set \(M(w)\) and, conversely, (ii) given \(M(w),\) reconstruct the word \(w.\) In the case of an infinite word \(x,\) we consider the following two functions: \(g_{x}\) that counts, for each \(n,\) the allowed factors of \(x\) of length \(n\) and \(f_{x}\) that counts, for each \(n,\) the minimal forbidden factors of \(x\) of length \(n.\) We address the following general problem: what information about the structure of \(x\) can be derived from the pair (\(g_{x},f_{x})?\) We prove that these two functions characterize, up to the automorphism exchanging the two letters, the language of factors of each single infinite Sturmian word. Cited in 22 Documents MSC: 68R15 Combinatorics on words Keywords:minimal forbidden factors; infinite Sturmian word PDFBibTeX XMLCite \textit{F. Mignosi} et al., Theor. Comput. Sci. 273, No. 1--2, 99--117 (2002; Zbl 0997.68093) Full Text: DOI Online Encyclopedia of Integer Sequences: The infinite Fibonacci word: start with 1, repeatedly apply the morphism 1->12, 2->1, take limit; or, start with S(0)=2, S(1)=1, and for n>1 define S(n)=S(n-1)S(n-2), then the sequence is S(oo). The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit). Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 0 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0’s and 1’s. Doubled Thue-Morse sequence: a(2n) = A010060(n), a(2n+1) = A010060(n). List of subwords of A003842 arranged in lexicographic order. Trebled Thue-Morse sequence: the A010060 sequence replacing 0 with 0,0,0 and 1 with 1,1,1. Doubled Fibonacci word: the A003842 sequence replacing 1 with 1,1 and 2 with 2,2. Erroneous version of A005942. List of minimal forbidden subwords of the Fibonacci word A003482. References: [1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Data Structures and Algorithms (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0307.68053 [2] Allouche, J.-P., Sur la complexité des suites infinies, Bull. Belg. Math. Soc., 1, 133-143 (1994) · Zbl 0803.68094 [3] Béal, M.-P.; Mignosi, F.; Restivo, A., Minimal Forbidden words and symbolic dynamics, (Puech, C.; Reischuk, R., STACS’96, Lecture Notes in Computer Science, vol. 1046 (1996), Springer: Springer Berlin), 555-566 · Zbl 1379.68213 [4] Béal, M.-P.; Mignosi, F.; Restivo, A.; Sciortino, M., Forbidden words in Symbolic Dynamics, Adv. Appl. Math., 25, 163-193 (2000) · Zbl 0965.37014 [5] J. Berstel, Fibonacci words – a survey, in: G. Rozenberg, A. Salomaa (Eds.), The Book of L, Springer, Berlin, 1986.; J. Berstel, Fibonacci words – a survey, in: G. Rozenberg, A. Salomaa (Eds.), The Book of L, Springer, Berlin, 1986. [6] J. Berstel, P. Séébold, Sturmian words, in: M. Lothaire (Ed.), Algebraic Combinatorics on Words, Cambridge University Press, Cambridge (Chapter 2), to appear. Available at http://www-igm.univ-mlv.fr \(/̃\); J. Berstel, P. Séébold, Sturmian words, in: M. Lothaire (Ed.), Algebraic Combinatorics on Words, Cambridge University Press, Cambridge (Chapter 2), to appear. Available at http://www-igm.univ-mlv.fr \(/̃\) [7] Blumer, A.; Blumer, J.; Ehrenfeucht, A.; Haussler, D.; Chen, M. T.; Seiferas, J., The smallest automaton recognizing the subwords of a text, Theoret. Comput. Sci., 40, 31-55 (1985) · Zbl 0574.68070 [8] Brlek, S., Enumeration of factors in the Thue-Morse word, Discrete Appl. Math., 24, 83-96 (1989) · Zbl 0683.20045 [9] A. Carpi, A. de Luca. Words and special factors, Theoret. Comput. Sci., to appear.; A. Carpi, A. de Luca. Words and special factors, Theoret. Comput. Sci., to appear. · Zbl 0973.68191 [10] Cassaigne, J., Complexité et facteurs spéciaux, Bull. Belg. Math. Soc., 4, 67-88 (1997) · Zbl 0921.68065 [11] Choffrut, C.; Karhumäki, J., Combinatorics on words, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 1 (1997), Springer: Springer Berlin), 329-438, (Chapter 6) [12] Crochemore, M.; Hancart, C., Automata for matching patterns, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 2 (1997), Springer: Springer Berlin), 399-462, (Chapter 9) [13] Crochemore, M.; Mignosi, F.; Restivo, A., Automata and forbidden words, Inform. Process Lett., 67, 111-117 (1998) · Zbl 1339.68145 [14] Crochemore, M.; Mignosi, F.; Restivo, A.; Salemi, S., Data Compression using antidictionaries, (Wiedermann, J.; van Emde Boas, P.; Nielsen, M., ICALP’99, Lecture Notes in Computer Science, vol. 1644 (1999), Springer: Springer Berlin), 261-270 [15] M. Crochemore, F. Mignosi, A. Restivo, S. Salemi, Data compression using antidictionaries, in: J.A. Storer (Ed.), Proceedings of the IEEE, Special Issue on Lossless Data Compression, Vol. 88, 11 (2000) 1756-1768.; M. Crochemore, F. Mignosi, A. Restivo, S. Salemi, Data compression using antidictionaries, in: J.A. Storer (Ed.), Proceedings of the IEEE, Special Issue on Lossless Data Compression, Vol. 88, 11 (2000) 1756-1768. [16] De Brujin, N. G., A combinatorial problem, Nederl. Akad. Wetensch. Proc., 49, 758-764 (1946) · Zbl 0060.02701 [17] de Luca, A.; Mignosi, F., Some combinatorial properties of Sturmian words, Theoret. Comput. Sci., 136, 361-385 (1994) · Zbl 0874.68245 [18] de Luca, A.; Mione, L., On bispecial factors of the Thue-Morse word, Inform. Process. Lett., 49, 179-183 (1994) · Zbl 0795.68159 [19] de Luca, A.; Varricchio, S., Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci., 63, 333-348 (1989) · Zbl 0671.10050 [20] Eilenberg, S., Automata, Languages and Machines, vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045 [21] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1980), Oxford University Press: Oxford University Press Oxford · Zbl 0020.29201 [22] G. Rauzy, Mots infinis en arithmétique, in: M .Nivat, D. Perrin (Eds.), Automata on Infinite Words, Lecture Notes in Computer Science, vol. 192, Springer, Berlin, 1984.; G. Rauzy, Mots infinis en arithmétique, in: M .Nivat, D. Perrin (Eds.), Automata on Infinite Words, Lecture Notes in Computer Science, vol. 192, Springer, Berlin, 1984. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.