Search
Now showing items 11-20 of 25
Infinite words containing squares at every position
(EDP Sciences, 2010)
Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve ...
Further applications of a power series method for pattern avoidance
(The Electronic Journal of Combinatorics, 2011-06-21)
In combinatorics on words, a word w over an alphabet ∑ is said to avoid a pattern
p over an alphabet ∆ if there is no factor x of w and no non-erasing morphism h
from ∆* to ∑* such that h(p) = x. Bell and Goh have recently ...
The minimal automaton recognizing mN in a linear numeration system
(Integers, 2011-12-02)
We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component ...
Abelian complexity of fixed point of morphism 0 -> 012, 1 -> 02, 2 -> 1
(2016-02-14)
We study the combinatorics of vtm, a variant of the Thue-Morse word generated by the non-uniform morphism 0 -> 012,1 -> 02,2 -> 1 starting with 0. This infinite ternary sequence appears a lot in the literature and finds ...
Cyclic Complexity of Some Infinite Words and Generalizations
(Integers, 2018-03)
Cassaigne et al. introduced the cyclic complexity function c_x(n), which gives the number of cyclic conjugacy classes of length-n factors of a word x. We study the behavior of this function for the Fibonacci word f and the ...
Shuffling and unshuffling
(Bulletin of the European Association for Theoretical Computer Science, 2012)
We consider various shuffling and unshuffling operations on languages and words, and examine their closure properties. Although the main goal is to provide some good and novel exercises and examples for undergraduate formal ...
The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially
(2004-06-19)
We show that the number of ternary words of length n avoiding abelian cubes grows
faster than r^n, where r = 2^{1/24}
Binary Words Containing Infinitely Many Overlaps
(The Electronic Journal of Combinatorics, 2006-09-22)
We characterize the squares occurring in infinite overlap-free binary words and construct various α power-free binary words containing infinitely many overlaps.
For each a > 2 there is an Infinite Binary Word with Critical Exponent a
(The Electronic Journal of Combinatorics, 2008-08-31)
The critical exponent of an infinite word w is the supremum of all rational numbers α such that w contains an α-power. We resolve an open question of Krieger and Shallit by showing that for each α>2 there is an infinite ...
A family of formulas with reversal of high avoidability index
(World Scientific, 2017)
We present an infinite family of formulas with reversal whose avoidability index is bounded between 4 and 5, and we show that several members of the family have avoidability index 5. This family is particularly interesting ...