James D. Currie: Recent submissions
Now showing items 2139 of 39

The Complexity of the Simplex Algorithm
(Carleton UniversityCarleton University, 198408)The thesis begins by giving background in linear programming and Simplex methods. Topics covered include the duality theorem, Lemke's algorithm, and the pathological programs of KleeMinty. Because of the bad behaviour ... 
Class Numbers and Biquadratic Reciprocity
(Cambridge University Press, 1982) 
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 ... 
Abelian complexity of fixed point of morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1
(Integers, 20140220)We study the combinatorics of vtm, a variant of the ThueMorse word generated by the nonuniform morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1 starting with 0. This infinite ternary sequence appears a lot in the literature and finds ... 
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 ... 
Dejean's conjecture holds for n ≥ 27
(EDP Sciences, 2009)We show that Dejean’s conjecture holds for n ≥ 27. This brings the final resolution of the conjecture by the approach of Moulin Ollagnier within range of the computationally feasible. 
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 ... 
Cubefree words with many squares
(Discrete Mathematics and Theoretical Computer Science, 20140513)We construct infinite cubefree binary words containing exponentially many distinct squares of length n . We also show that for every positive integer n , there is a cubefree binary square of length 2n. 
Combinatorics and Algorithmics of Strings
(Dagstuhl Publishing, 20140309)Strings (aka sequences or words) form the most basic and natural data structure. They occur whenever information is electronically transmitted (as bit streams), when natural language text is spoken or written down (as words ... 
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 ... 
Extremal Infinite OverlapFree Binary Words
(The Electronic Journal of Combinatorics, 19980503)Let t be the infinite fixed point, starting with 1, of the morphism μ:0→01, 1→10. An infinite word over {0,1} is said to be overlapfree if it contains no factor of the form axaxa, where a∈{0,1} and x∈{0,1}∗. We prove that ... 
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 ... 
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. 
Binary Words Containing Infinitely Many Overlaps
(The Electronic Journal of Combinatorics, 20060922)We characterize the squares occurring in infinite overlapfree binary words and construct various α powerfree 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, 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 ... 
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 ... 
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. 
Avoidability index for binary patterns with reversal
(The Electronic Journal of Combinatorics, 20160219)For every pattern p over the alphabet {x, x^R, y, y^R}, we specify the least k such that p is kavoidable.