×

Avoiding abelian powers in binary words with bounded abelian complexity. (English) Zbl 1223.68089

Two words are abelian equivalent if they contain the same letters with the same number of occurences. The abelian complexity of a word is the number of its subwords of length \(n\) that are pairwise abelian inequivalent. A nonempty word is an abelian \(k\)-power, if it is a concatenation of \(k\) pairwise abelian equivalent subwords.
The authors consider the problem of the frequency of abelian \(k\)-powers in words having bounded abelian complexity and prove the followings theorems:
Every suffix of the well-known Thue-Morse word begins in an abelian \(k\)-power for all positive integers \(k\);
There exists a uniformly recurrent infinite word with bounded abelian complexity that does not begin in an abelian square;
There exists a uniformly recurrent infinite word with bounded abelian complexity in which there are infinitely many positions where no abelian square occurs.
The authors also consider the effect of morphisms on abelian complexity and show that the bounded property of abelian complexity is preserved by morphisms.
Finally, the authors present an open problem, namely whether there exists an infinite binary word that avoids abelian squares in positions that occur in bounded gaps, and prove that it is equivalent to a well-known open problem proposed independently by G. Pirillo and S. Varricchio [“On uniformly repetitive semigroups”, Semigroup Forum 49, No. 1, 125–129 (1994; Zbl 0805.20052)] and L. Halbeisen and N. Hungerbühler [“An application of van der Waerden’s theorem in additive number theory”, Integers 0, Paper A07, 5 p. (2000; Zbl 0962.11017)], asking whether there exists an infinite word over a finite set of integers such that no two consecutive blocks of the same length have the same sum.

MSC:

68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Richomme G., J. London Math. Soc.
[2] Currie J., Adv. in Appl. Math.
[3] DOI: 10.2307/2371431 · Zbl 0022.34003
[4] DOI: 10.1016/j.aam.2010.01.006 · Zbl 1203.68131
[5] DOI: 10.1051/ita/2010017 · Zbl 1211.68303
[6] DOI: 10.1007/BF02573477 · Zbl 0805.20052
[7] Halbeisen L., Integers 0 pp #A07–
[8] DOI: 10.1016/0097-3165(74)90041-7 · Zbl 0279.05001
[9] DOI: 10.1016/0097-3165(79)90044-X · Zbl 0437.05011
[10] Shallit J., A Second Course in Formal Languages and Automata Theory (2009) · Zbl 1163.68025
[11] Allouche J.-P., Electron. J. Combin. 5 pp #R27–
[12] DOI: 10.1017/CBO9781107341005
[13] DOI: 10.1016/S0304-3975(03)00092-6 · Zbl 1059.68083
[14] DOI: 10.1016/S0012-365X(97)00029-0 · Zbl 0895.68087
[15] DOI: 10.1016/j.tcs.2007.10.027 · Zbl 1133.68036
[16] Szemerédi E., Acta Arith. 27 pp 299–
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.