Abstract
Denote by the class of standard Sturmian words. It is a class of highly compressible words extensively studied in combinatorics of words, including the well known Fibonacci words. The suffix automata for these words have a very particular structure. This implies a simple characterization (described in the paper by the Structural Lemma) of the periods of runs (maximal repetitions) in Sturmian words. Using this characterization we derive an explicit formula for the number ρ(w) of runs in words , with respect to their recurrences (directive sequences). We show that \(\frac{\rho(w)}{|w|}\le \frac{4}{5} \textrm{\ for each\ }\ w\in {\cal S},\) and there is an infinite sequence of strictly growing words \(w_k\in {\cal S}\) such that \(\lim_{k\rightarrow \infty}\ \frac{\rho(w_k)}{|w_k|}\ =\ \frac{4}{5}\). The complete understanding of the function ρ for a large class of complicated words is a step towards better understanding of the structure of runs in words. We also show how to compute the number of runs in a standard Sturmian word in linear time with respect to the size of its compressed representation (recurrences describing the word). This is an example of a very fast computation on texts given implicitly in terms of a special grammar-based compressed representation (usually of logarithmic size with respect to the explicit text).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Baturo, P., Rytter, W.: Occurrence and lexicographic properties of standard Sturmian words. In: LATA 2007 (2007)
Berstel, J., Seebold, P.: Sturmian words. In: Lothaire, M. (ed.) Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, ch.2, vol. 90, pp. 45–110. Cambridge University Press, Cambridge (2002)
Berstel, J., Karhumäki, J.: Combinatorics on words - a tutorial. Bull. EATCS 79, 178–228 (2003)
Iliopoulos, C., Moore, D., Smyth, W.F.: Characterization of the Squares in a Fibonacci String. Theor. Comput. Sci. 172(1-2), 281–291 (1997)
Crochemore, M., Ilie, L.: Analysis of Maximal Repetitions in Strings. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 465–476. Springer, Heidelberg (2007)
Crochemore, M., Ilie, L., Tinta, I.: Towards a solution to the ”runs” conjecture (to be published, CPM 2008)
Franek, F., Simpson, R.J., Smyth, W.F.: The maximum number of runs in a string. In: Miller, M., Park, K. (eds.) Proceeding of 14th Australian Workshop on Combinatorial Algorithms, pp. 26–35 (2003)
Franek, F., Karaman, A., Smyth, W.F.: Repetitions in Sturmian strings. Theoretical Computer Science 249(2), 289–303 (2000)
Kolpakov, R., Kucherov, G.: On Maximal Repetitions in Words. In: Ciobanu, G., Păun, G. (eds.) FCT 1999. LNCS, vol. 1684, pp. 374–385. Springer, Heidelberg (1999)
Kolpakov, R., Kucherov, G.: Finding Maximal Repetitions in a Word in Linear Time. In: FOCS 1999, pp. 596–604 (1999)
Rytter, W.: The number of runs in a string. Information and Computation 205(9), 1459–1469 (2007)
Rytter, W.: Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 15–27. Springer, Heidelberg (2004)
Rytter, W.: The structure of subword graphs and suffix trees of Fibonacci words. Theoretical Computer Science 363(2), 211–223 (2006)
Sciortino, M., Zamboni, L.: Suffix Automata and Standard Sturmian Words. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 382–398. Springer, Heidelberg (2007)
Smyth, B.: Computing patterns in strings. Addison Wesley, Reading (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baturo, P., Piątkowski, M., Rytter, W. (2008). The Number of Runs in Sturmian Words. In: Ibarra, O.H., Ravikumar, B. (eds) Implementation and Applications of Automata. CIAA 2008. Lecture Notes in Computer Science, vol 5148. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70844-5_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-70844-5_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70843-8
Online ISBN: 978-3-540-70844-5
eBook Packages: Computer ScienceComputer Science (R0)