Browsing James D. Currie by Title
Now showing items 2140 of 40

Extremal words in morphic subshifts
(Elsevier, 20140122)Given an infinite word x over an alphabet A, a letter b occurring in x, and a total order \sigma on A, we call the smallest word with respect to \sigma starting with b in the shift orbit closure of x an extremal word of ... 
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 ... 
For each a > 2 there is an Infinite Binary Word with Critical Exponent a
(The Electronic Journal of Combinatorics, 20080831)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 ... 
Growth rate of binary words avoiding xxxR
(Elsevier, 201601)Abstract Consider the set of those binary words with no nonempty factors of the form xxx^R. Du, Mousavi, Schaeffer, and Shallit asked whether this set of words grows polynomially or exponentially with length. In this ... 
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 ... 
Least Periods of Factors of Infinite Words
(EDP Sciences, 2009)We show that any positive integer is the least period of a factor of the ThueMorse word. We also characterize the set of least periods of factors of a Sturmian word. In particular, the corresponding set for the Fibonacci ... 
The metric dimension and metric independence of a graph
(The Charles Babbage Research Centre, 2001)A vertex x of a graph G resolves two vertices u and v of G if the distance from x to u does not equal the distance from x to v. A set S of vertices of G is a resolving set for G if every two distinct vertices of G are ... 
Non repetitive walks in graphs and digraphs
(The University of CalgaryUniversity of Calgary, 198706)A word $w$ over alphabet $\Sigma$ is {\em nonrepetitive} if we cannot write $w=abbc$, $a,b,c\in\Sigma^*$, $b\ne\epsilon$. That is, no subword of $w$ appears twice in a row in $w$. In 1906, Axel Thue, the Norwegian number ... 
NonRepetitive Tilings
(The Electronic Journal of Combinatorics, 20020703)In 1906 Axel Thue showed how to construct an infinite nonrepetitive (or squarefree) word on an alphabet of size 3. Since then this result has been rediscovered many times and extended in many ways. We present a twodimensional ... 
A Note on Antichains of Words
(The Electronic Journal of Combinatorics, 19951014)We can compress the word 'banana' as xyyz, where x= 'b', y= 'an',z= 'a'. We say that 'banana' encounters yy. Thus a 'coded' version of yy shows up in 'banana'. The relation 'u encounters w' is transitive, and thus generates ... 
The number of order–preserving maps of fences and crowns
(Springer, 199106)We perform an exact enumeration of the orderpreserving maps of fences (zigzags) and crowns (cycles). From this we derive asymptotic results. 
The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially
(20040619)We show that the number of ternary words of length n avoiding abelian cubes grows faster than r^n, where r = 2^{1/24} 
On avoidability of formulas with reversal
(EDP Sciences, 20180213)While a characterization of unavoidable formulas (without reversal) is wellknown, little is known about the avoidability of formulas with reversal in general. In this article, we characterize the unavoidable formulas ... 
Squarefree Words with Squarefree Selfshuffles
(The Electronic Journal of Combinatorics, 20140112)We answer a question of Harju: For every n ≥ 3 there is a squarefree ternary word of length n with a squarefree selfshuffle. 
Suffix conjugates for a class of morphic subshifts
(Cambridge University Press, 201509)Let A be a finite alphabet and f: A^* > A^* be a morphism with an iterative fixed point f^\omega(\alpha), where \alpha{} is in A. Consider the subshift (X, T), where X is the shift orbit closure of f^\omega(\alpha) and ... 
A Ternary Squarefree Sequence Avoiding Factors Equivalent to abcacba
(The Electronic Journal of Combinatorics, 20160527)We solve a problem of Petrova, finalizing the classification of letter patterns avoidable by ternary squarefree words; we show that there is a ternary squarefree word avoiding letter pattern xyzxzyx. In fact, we characterize ... 
There are Ternary Circular SquareFree Words of Length n for n ≥ 18
(The Electronic Journal of Combinatorics, 20021011)There are circular squarefree words of length n on three symbols for n≥18. This proves a conjecture of R. J. Simpson. 
There Exist Binary Circular 5/2+ Power Free Words of Every Length
(The Electronic Journal of Combinatorics, 20040123)We show that there exist binary circular 5/2+ power free words of every length. 
Unary patterns under permutations
(Elsevier, 20180604)Thue characterized completely the avoidability of unary patterns. Adding function variables gives a general setting capturing avoidance of powers, avoidance of patterns with palindromes, avoidance of powers under coding, ... 
Words without NearRepetitions
(Canadian Mathematical Society, 19920601)We find an infinite word w on four symbols with the following property: Two occurrences of any block in w must be separated by more than the length of the block. That is, in any subword of w of the form xyx, the length of ...