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

Avoiding Patterns in the Abelian Sense
(Canadian Mathematical Society, 200108)We classify all 3 letter patterns that are avoidable in the abelian sense. A short list of four letter patterns for which abelian avoidance is undecided is given. Using a generalization of Zimin words we deduce some ... 
Avoiding three consecutive blocks of the same size and same sum
(Association of Computing Machinery, 201404)We show that there exists an inﬁnite word over the alphabet {0,1,3,4} containing no three consecutive blocks of the same size and the same sum. This answers an open problem of Pirillo and Varricchio from1994. 
Binary Words Avoiding xxRx and Strongly Unimodal Sequences
(20150914)In previous work, Currie and Rampersad showed that the growth of the number of binary words avoiding the pattern xxxR was intermediate between polynomial and exponential. We now show that the same result holds for the ... 
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. 
The Brachistochrone Problem: Mathematics for a Broad Audience via a Large Context Problem
(Montana Council of Teachers of Mathematics & Information Age Publishing, 2008)Large context problems (LCP) are useful in teaching the history of science. In this article we consider the brachistochrone problem in a context stretching from Euclid through the Bernoullis. We highlight a variety of ... 
A Characterization of Fractionally WellCovered Graphs
(Ars Combinatoria, 1991)A graph is called wellcovered if every maximal independent set has the same size. One generalization of independent sets in graphs is that of a fractional cover  attach nonnegative weights to the vertices and require ... 
Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101
(20200519)We characterize exactly the lengths of binary circular words containing no squares other than 00, 11, and 0101. 
Class Numbers and Biquadratic Reciprocity
(Cambridge University Press, 1982) 
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 ... 
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 ... 
Counting endomorphisms of crownlike orders
(Springer, 200212)The authors introduce the notion of crownlike orders and introduce powerful tools for counting the endomorphisms of orders of this type. 
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. 
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. 
A direct proof of a result of Thue
(Utilitas Mathematica, 1984) 
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 ... 
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 ...