×

Words and forbidden factors. (English) Zbl 0997.68093

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.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

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.