Now showing items 1-9 of 9

    • Abelian complexity of fixed point of morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1 

      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 ...
    • Avoiding approximate repetitions with respect to the longest common subsequence distance 

      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. ...
    • 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 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 ...
    • 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 ...
    • Multi-dimensional sets recognizable in all abstract numeration systems 

      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.
    • 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 ...
    • Shuffling and unshuffling 

      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 ...