WinnSpace Repository

Department of Mathematics and Statistics

Department of Mathematics and Statistics

Recent Submissions

  • Krawchuk, Colin; Rampersad, Narad (Integers, 2018-03)
    Cassaigne et al. introduced the cyclic complexity function c_x(n), which gives the number of cyclic conjugacy classes of length-n factors of a word x. We study the behavior of this function for the Fibonacci word f and the ...
  • Rampersad, Narad (University of Waterloo, 2007)
    The study of combinatorics on words dates back at least to the beginning of the 20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains ...
  • Rampersad, Narad (The Electronic Journal of Combinatorics, 2011-06-21)
    In combinatorics on words, a word w over an alphabet ∑ is said to avoid a pattern p over an alphabet ∆ if there is no factor x of w and no non-erasing morphism h from ∆* to ∑* such that h(p) = x. Bell and Goh have recently ...
  • Charlier, Émilie; Rampersad, Narad; Rigo, Michel; Waxweiler, Laurent (Integers, 2011-12-02)
    We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component ...
  • Charlier, Émilie; Lacroix, Anne; Rampersad, Narad (EDP Sciences, 2011)
    We prove that the subsets of Nd that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.
  • Henshall, Dane; Rampersad, Narad; Shallit, Jeffrey (Bulletin of the European Association for Theoretical Computer Science, 2012)
    We consider various shuffling and unshuffling operations on languages and words, and examine their closure properties. Although the main goal is to provide some good and novel exercises and examples for undergraduate formal ...
  • Lacroix, Anne; Rampersad, Narad (Discrete Mathematics and Theoretical Computer Science, 2013)
    If L is a language, the automaticity function AL(n) (resp. NL(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all ...
  • Blanchet-Sadri, F.; Currie, James D.; Rampersad, Narad; Fox, Nathan (Integers, 2014-02-20)
    We study the combinatorics of vtm, a variant of the Thue-Morse word generated by the non-uniform morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1 starting with 0. This infinite ternary sequence appears a lot in the literature and finds ...
  • Borchert, Adam; Rampersad, Narad (The Electronic Journal of Combinatorics, 2015-10-30)
    Motivated by a conjecture of Frid, Puzynina, and Zamboni, we investigate infinite words with the property that for infinitely many n, every length-n factor is a product of two palindromes. We show that every Sturmian word ...
  • Camungol, Serina; Rampersad, Narad (Mathematical Sciences Publishers, 2015-09-17)
    Ochem, Rampersad, and Shallit gave various examples of infinite words avoiding what they called approximate repetitions. An approximate repetition is a factor of the form x x', where x and x' are close to being identical. ...
  • 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 ...
  • 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.
  • 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 ...
  • 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.
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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.

View more