Abstract
We investigate questions related to the presence of primitive words and Lyndon words in automatic and linearly recurrent sequences. We show that the Lyndon factorization of a k-automatic sequence is itself k-automatic. We also show that the function counting the number of primitive factors (resp., Lyndon factors) of length n in a k-automatic sequence is k-regular. Finally, we show that the number of Lyndon factors of a linearly recurrent sequence is bounded.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Allouche, J.-P., Rampersad, N., Shallit, J.: Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410, 2795–2803 (2009)
Allouche, J.-P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003)
Allouche, J.-P., Shallit, J.O.: The ring of k-regular sequences. Theoret. Comput. Sci. 98, 163–197 (1992)
Černý, A.: Lyndon factorization of generalized words of Thue. Discrete Math. & Theoret. Comput. Sci. 5, 17–46 (2002)
Charlier, É., Rampersad, N., Shallit, J.: Enumeration and Decidable Properties of Automatic Sequences. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 165–179. Springer, Heidelberg (2011)
Cobham, A.: Uniform tag sequences. Math. Systems Theory 6, 164–192 (1972)
Durand, F.: A characterization of substitutive sequences using return words. Discrete Math. 179, 89–101 (1998)
Durand, F., Host, B., Skau, C.: Substitution dynamical systems, bratteli diagrams, and dimension groups. Ergod. Theory & Dynam. Sys. 19, 953–993 (1999)
Duval, J.P.: Factorizing words over an ordered alphabet. J. Algorithms 4, 363–381 (1983)
Goč, D., Henshall, D., Shallit, J.: Automatic Theorem-Proving in Combinatorics on Words. In: Moreira, N., Reis, R. (eds.) CIAA 2012. LNCS, vol. 7381, pp. 180–191. Springer, Heidelberg (2012)
Goč, D., Schaeffer, L., Shallit, J.: The subword complexity of k-automatic sequences is k-synchronized (June 23, 2012) (preprint), http://arxiv.org/abs/1206.5352
Ido, A., Melançon, G.: Lyndon factorization of the Thue-Morse word and its relatives. Discrete Math. & Theoret. Comput. Sci. 1, 43–52 (1997)
Melançon, G.: Lyndon Factorization of Infinite Words. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 147–154. Springer, Heidelberg (1996)
Schaeffer, L., Shallit, J.: The critical exponent is computable for automatic sequences. Int. J. Found. Comput. Sci. (2012) (to appear)
Séébold, P.: Lyndon factorization of the Prouhet words. Theoret. Comput. Sci. 307, 179–197 (2003)
Shallit, J.: The critical exponent is computable for automatic sequences. In: Ambroz, P., Holub, S., Másaková, Z. (eds.) Proceedings 8th International Conference Words 2011. Elect. Proc. Theor. Comput. Sci., vol. 63, pp. 231–239 (2011)
Siromoney, R., Mathew, L., Dare, V., Subramanian, K.: Infinite Lyndon words. Inform. Process. Lett. 50, 101–104 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goč, D., Saari, K., Shallit, J. (2013). Primitive Words and Lyndon Words in Automatic and Linearly Recurrent Sequences. In: Dediu, AH., Martín-Vide, C., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2013. Lecture Notes in Computer Science, vol 7810. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37064-9_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-37064-9_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37063-2
Online ISBN: 978-3-642-37064-9
eBook Packages: Computer ScienceComputer Science (R0)