Now showing items 18-37 of 40

    • 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 ...
    • The number of order–preserving maps of fences and crowns 

      Currie, James; Visentin, Terry I. (Springer, 1991-06)
      We perform an exact enumeration of the order-preserving maps of fences (zig-zags) and crowns (cycles). From this we derive asymptotic results.
    • The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially 

      Currie, James; Rampersad, Narad; Aberkane, Ali (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}
    • On avoidability of formulas with reversal 

      Currie, James D.; Mol, Lucas; Rampersad, Narad (EDP Sciences, 2018-02-13)
      While a characterization of unavoidable formulas (without reversal) is well-known, little is known about the avoidability of formulas with reversal in general. In this article, we characterize the unavoidable formulas ...
    • Square-free Words with Square-free Self-shuffles 

      Currie, James D.; Saari, Kalle (The Electronic Journal of Combinatorics, 2014-01-12)
      We answer a question of Harju: For every n ≥ 3 there is a square-free ternary word of length n with a square-free self-shuffle.
    • Suffix conjugates for a class of morphic subshifts 

      Currie, James D.; Rampersad, Narad; Saari, Kalle (Cambridge University Press, 2015-09)
      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 Square-free Sequence Avoiding Factors Equivalent to abcacba 

      Currie, James D. (The Electronic Journal of Combinatorics, 2016-05-27)
      We solve a problem of Petrova, finalizing the classification of letter patterns avoidable by ternary square-free words; we show that there is a ternary square-free word avoiding letter pattern xyzxzyx. In fact, we characterize ...
    • There are Ternary Circular Square-Free Words of Length n for n ≥ 18 

      Currie, James D. (The Electronic Journal of Combinatorics, 2002-10-11)
      There are circular square-free words of length n on three symbols for n≥18. This proves a conjecture of R. J. Simpson.