Abstract
We say that an infinite word w is weakly abelian periodic if it can be factorized into finite words with the same frequencies of letters. In this paper we study properties of weak abelian periodicity, and its relations with balance and frequency. We establish necessary and sufficient conditions for weak abelian periodicity of fixed points of uniform binary morphisms. Also, we discuss weak abelian periodicity in minimal subshifts.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Adamczewski, B.: Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307, 47–75 (2003)
Avgustinovich, S., Karhumäki, J., Puzynina, S.: On abelian versions of critical factorization theorem. RAIRO - Theoretical Informatics and Applications 46, 3–15 (2012)
Cassaigne, J., Karhumäki, J.: Toeplitz Words, Generalized Periodicity and Periodically Iterated Morphisms. Eur. J. Comb. 18(5), 497–510 (1997)
Cassaigne, J., Richomme, G., Saari, K., Zamboni, L.Q.: Avoiding Abelian powers in binary words with bounded Abelian complexity. Int. J. Found. Comput. Sci. 22(4), 905–920 (2011)
Constantinescu, S., Ilie, L.: Fine and Wilf’s theorem for abelian periods. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 89, 167–170 (2006)
Durand, F.: A characterization of substitutive sequences using return words. Discrete Mathematics 179(1-3), 89–101 (1998)
Erdös, P.: Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6, 221–254 (1961)
Gerver, J.L., Ramsey, L.T.: On certain sequences of lattice points. Pacific J. Math. 83(2), 357–363 (1979)
Holton, C., Zamboni, L.Q.: Geometric Realizations Of Substitutions. Bull. Soc. Math. France 126, 149–179 (1998)
Keränen, V.: Abelian squares are avoidable on 4 letters. In Automata, languages and programming. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 41–52. Springer, Heidelberg (1992)
Krajnev, V.A.: Words that do not contain consecutive factors with equal frequencies of letters. Metody Discretnogo Analiza v Reshenii Kombinatornyh Zadach 34, 27–37 (1980)
Lothaire, M.: Algebraic combinatorics on words. Cambridge University Press (2002)
Puzynina, S., Zamboni, L.Q.: Abelian returns in Sturmian words. J. Combin. Theory, Ser. A, V. 120(2), 390–408 (2013)
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
Avgustinovich, S., Puzynina, S. (2013). Weak Abelian Periodicity of Infinite Words. In: Bulatov, A.A., Shur, A.M. (eds) Computer Science – Theory and Applications. CSR 2013. Lecture Notes in Computer Science, vol 7913. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38536-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-38536-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38535-3
Online ISBN: 978-3-642-38536-0
eBook Packages: Computer ScienceComputer Science (R0)