Abstract
In this paper we investigate local-to-global phenomena for a new family of complexity functions of infinite words indexed by k ∈ ℕ1 ∪ { + ∞ } where ℕ1 denotes the set of positive integers. Two finite words u and v in A * are said to be k-abelian equivalent if for all x ∈ A * of length less than or equal to k, the number of occurrences of x in u is equal to the number of occurrences of x in v. This defines a family of equivalence relations ~ k on A *, bridging the gap between the usual notion of abelian equivalence (when k = 1) and equality (when k = + ∞). Given an infinite word w ∈ A ω, we consider the associated complexity function \(\mathcal P^{(k)}_w : \mathbb N_1 \rightarrow \mathbb N_1\) which counts the number of k-abelian equivalence classes of factors of w of length n. As a whole, these complexity functions have a number of common features: Each gives a characterization of periodicity in the context of bi-infinite words, and each can be used to characterize Sturmian words in the framework of aperiodic one-sided infinite words. Nevertheless, they also exhibit a number of striking differences, the study of which is one of the main topics of our paper.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allouche, J.P., Arnold, A., Berstel, J., Brlek, S., Jockusch, W., Plouffe, S., Sagan, B.E.: A relative of the Thue-Morse sequence. Discrete Math. 139(1-3), 455–461 (1995)
Allouche, J.P., Shallit, J.: The ring of k-regular sequences. Theoret. Comput. Sci. 98(2), 163–197 (1992)
Blanchet-Sadri, F., Currie, J., Rampersad, N., Fox, N.: Abelian complexity of fixed point of morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1. Integers 14, A11 (2014)
Cassaigne, J., Richomme, G., Saari, K., Zamboni, L.Q.: Avoiding Abelian powers in binary words with bounded Abelian complexity. Internat. J. Found. Comput. Sci. 22(4), 905–920 (2011)
Coven, E.M., Hedlund, G.A.: Sequences with minimal block growth. Math. Systems Theory 7, 138–153 (1973)
Currie, J., Rampersad, N.: Recurrent words with constant Abelian complexity. Adv. in Appl. Math. 47(1), 116–124 (2011)
Damanik, D.: Local symmetries in the period-doubling sequence. Discrete Appl. Math. 100(1-2), 115–121 (2000)
Dekking, M.: Strongly nonrepetitive sequences and progression-free sets. J. Combin. Theory Ser. A 27(2), 181–185 (1979)
Greinecker, F.: On the 2-abelian complexity of Thue-Morse subwords (Preprint), arXiv:1404.3906
Huova, M., Karhumäki, J.: Observations and problems on k-abelian avoidability. In: Combinatorial and Algorithmic Aspects of Sequence Processing (Dagstuhl Seminar 11081), pp. 2215–2219 (2011)
Huova, M., Karhumäki, J., Saarela, A.: Problems in between words and abelian words: k-abelian avoidability. Theoret. Comput. Sci. 454, 172–177 (2012)
Huova, M., Karhumäki, J., Saarela, A., Saari, K.: Local squares, periodicity and finite automata. In: Calude, C.S., Rozenberg, G., Salomaa, A. (eds.) Rainbow of Computer Science. LNCS, vol. 6570, pp. 90–101. Springer, Heidelberg (2011)
Karhumäki, J., Puzynina, S., Saarela, A.: Fine and Wilf’s theorem for k-abelian periods. Internat. J. Found. Comput. Sci. 24(7), 1135–1152 (2013)
Karhumäki, J., Saarela, A., Zamboni, L.Q.: On a generalization of Abelian equivalence and complexity of infinite words. J. Combin. Theory Ser. A 120(8), 2189–2206 (2013)
Keränen, V.: Abelian squares are avoidable on 4 letters. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 41–52. Springer, Heidelberg (1992)
Mercaş, R., Saarela, A.: 3-abelian cubes are avoidable on binary alphabets. In: Béal, M.-P., Carton, O. (eds.) DLT 2013. LNCS, vol. 7907, pp. 374–383. Springer, Heidelberg (2013)
Morse, M., Hedlund, G.A.: Symbolic dynamics. Amer. J. Math. 60(4), 815–866 (1938)
Morse, M., Hedlund, G.A.: Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62(1), 1–42 (1940)
Parreau, A., Rigo, M., Vandomme, E.: A conjecture on the 2-abelian complexity of the Thue-Morse word. In: Representing Streams II (2014)
Puzynina, S., Zamboni, L.Q.: Abelian returns in Sturmian words. J. Combin. Theory Ser. A 120(2), 390–408 (2013)
Richomme, G., Saari, K., Zamboni, L.Q.: Balance and Abelian complexity of the Tribonacci word. Adv. in Appl. Math. 45(2), 212–231 (2010)
Richomme, G., Saari, K., Zamboni, L.Q.: Abelian complexity of minimal subshifts. J. Lond. Math. Soc (2) 83(1), 79–95 (2011)
Saarela, A.: Ultimately constant abelian complexity of infinite words. J. Autom. Lang. Comb. 14(3-4), 255–258 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Karhumäki, J., Saarela, A., Zamboni, L.Q. (2014). Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence. In: Shur, A.M., Volkov, M.V. (eds) Developments in Language Theory. DLT 2014. Lecture Notes in Computer Science, vol 8633. Springer, Cham. https://doi.org/10.1007/978-3-319-09698-8_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-09698-8_18
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09697-1
Online ISBN: 978-3-319-09698-8
eBook Packages: Computer ScienceComputer Science (R0)