Now showing items 11-30 of 40

    • A Characterization of Fractionally Well-Covered Graphs 

      Currie, James; Nowakowski, Richard (Ars Combinatoria, 1991)
      A graph is called well-covered 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 

      Currie, James D.; Johnson, Jesse T. (2020-05-19)
      We characterize exactly the lengths of binary circular words containing no squares other than 00, 11, and 0101.
    • Class Numbers and Biquadratic Reciprocity 

      Williams, Kenneth S.; Currie, James D. (Cambridge University Press, 1982)
    • Combinatorics and Algorithmics of Strings 

      Crochemore, Maxime; Currie, James D.; Kucherov, Gregory; Nowotka, Dirk (Dagstuhl Publishing, 2014-03-09)
      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 

      Currie, James (Carleton UniversityCarleton University, 1984-08)
      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 Klee-Minty. Because of the bad behaviour ...
    • Counting endomorphisms of crown-like orders 

      Currie, James D.; Visentin, Terry I. (Springer, 2002-12)
      The authors introduce the notion of crown-like orders and introduce powerful tools for counting the endomorphisms of orders of this type.
    • Cubefree words with many squares 

      Currie, James D.; Rampersad, Narad (Discrete Mathematics and Theoretical Computer Science, 2014-05-13)
      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 

      Currie, James; Rampersad, Narad (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 

      Currie, James D. (Utilitas Mathematica, 1984)
    • Extremal Infinite Overlap-Free Binary Words 

      Allouche, Jean-Paul; Currie, James D.; Shallit, Jeffrey (The Electronic Journal of Combinatorics, 1998-05-03)
      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 overlap-free 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 

      Zamboni, Luca Q.; Saari, Kalle; Rampersad, Narad; Currie, James D. (Elsevier, 2014-01-22)
      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 

      Currie, James; Mol, Lucas; Rampersad, Narad (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 

      Currie, James D.; Rampersad, Narad (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 ...
    • Growth rate of binary words avoiding xxxR 

      Currie, James D.; Rampersad, Narad (Elsevier, 2016-01)
      Abstract Consider the set of those binary words with no non-empty 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 

      Currie, James; Rampersad, Narad (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 

      Currie, James D.; Saari, Kalle (EDP Sciences, 2009)
      We show that any positive integer is the least period of a factor of the Thue-Morse 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 

      Currie, James; Oellerman, Ortrud R. (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 

      Currie, James Daniel (The University of CalgaryUniversity of Calgary, 1987-06)
      A word $w$ over alphabet $\Sigma$ is {\em non-repetitive} 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 ...
    • Non-Repetitive Tilings 

      Currie, James D.; Simpson, Jamie (The Electronic Journal of Combinatorics, 2002-07-03)
      In 1906 Axel Thue showed how to construct an infinite non-repetitive (or square-free) word on an alphabet of size 3. Since then this result has been rediscovered many times and extended in many ways. We present a two-dimensional ...
    • A Note on Antichains of Words 

      Currie, James D. (The Electronic Journal of Combinatorics, 1995-10-14)
      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 ...