Article ID Journal Published Year Pages File Type
435709 Theoretical Computer Science 2015 8 Pages PDF
Abstract

We prove that 2-abelian-cubes are avoidable over a binary alphabet and that 3-abelian-squares are avoidable over a ternary alphabet, answering positively to two questions of Karhumäki et al. We also show the existence of infinite additive-cube-free words on several ternary alphabets. To achieve this, we give sufficient conditions for a morphism to be k-abelian-n-power-free (resp. additive-n-power-free), and then we give several morphisms which respect these conditions.Additionally, all our constructions show that the number of such words grows exponen-tially. As a corollary, we get a new lower bound of 31/19=1.059526…31/19=1.059526… for the growth rate of abelian-cube-free words.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,