Abstract
The Crochemore factorization was introduced by Crochemore for the design of a linear time algorithm to detect squares in a word. We give here the explicit description of the Crochemore factorization for some classes of infinite words, namely characteristic Sturmian words, (generalized) Thue-Morse words, and the period doubling sequence.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allouche, J.-P., Shallit, J.: Automatic Sequences. Cambridge University Press, Cambridge (2003)
Crochemore, M.: Recherche linéaire d’un carré dans un mot. Comptes Rendus Sci. Paris Sér. I Math. 296, 781–784 (1983)
Crochemore, M., Hancart, C., Lecroq, T.: Algorithmique du texte. Vuibert (2001)
Crochemore, M., Rytter, W.: Text Algorithms. The Clarendon Press, Oxford University Press (1994)
de Luca, A.: A division property of the Fibonacci word. Information Processing Letters 54, 307–312 (1995)
Kolpakov, R., Kucherov, G.: Periodic structures on words, in Lothaire. In: Applied Combinatorics on Words, Cambridge University Press, Cambridge (2005)
Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Transactions in Information Theory IT-22, 75–81 (1976)
Wen, Z.-X., Wen, Z.-Y.: Some properties of the singular words of the Fibonacci word. European Journal of Combinatorics 15, 587–598 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berstel, J., Savelli, A. (2006). Crochemore Factorization of Sturmian and Other Infinite Words. In: Královič, R., Urzyczyn, P. (eds) Mathematical Foundations of Computer Science 2006. MFCS 2006. Lecture Notes in Computer Science, vol 4162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11821069_14
Download citation
DOI: https://doi.org/10.1007/11821069_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37791-7
Online ISBN: 978-3-540-37793-1
eBook Packages: Computer ScienceComputer Science (R0)