Counting bordered partial words by critical positions.
Allen, Emily; Blanchet-Sadri, F.; Byrum, Cameron; Cucuringu, Mihai; Mercaş, Robert — 2011
The Electronic Journal of Combinatorics [electronic only]
Counting bordered partial words by critical positions.
5-abelian cubes are avoidable on binary alphabets
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 note on the number of squares in a partial word with one hole
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...
Binary patterns in binary cube-free words: Avoidability and growth
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