We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern . These types, , , and , differ by the factor complexity and the asymptotic frequency of the letter 0. Type has polynomial factor complexity and letter frequency . Type has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type is obtained from type ...
We present an algorithm which produces, in some cases, infinite words avoiding both large fractional repetitions and a given set of finite words. We use this method to show that all the ternary patterns whose avoidability index was left open in Cassaigne's thesis are 2-avoidable. We also prove that there exist exponentially many -free ternary words and -free 4-ary words. Finally we give small morphisms for binary words containing only the squares , 1 and (01)² and for binary words avoiding large...
The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids -powers for all . We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.
We prove two cases of a strong version of Dejean's conjecture involving extremal letter frequencies. The results are that there exist an infinite -free word over a 5 letter alphabet with letter frequency and an infinite -free word over a 6 letter alphabet with letter frequency .
The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids -powers for all . We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.
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