A -abelian cube is a word , where the factors , , and are either pairwise equal, or have the same multiplicities for every one of their factors of length at most . Previously it has been shown that -abelian cubes are avoidable over a binary alphabet for ≥ 8. Here it is proved that this holds for ≥ 5.
A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length is bounded by since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate squares in partial words with one hole, or sequences over a finite alphabet that have a “do not know” symbol or “hole”. A square in a partial word over a given alphabet has the form where is with , and consequently, such square is compatible with a...
The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted upper...
Page 1