Now showing items 21-40 of 69

    • Squares and overlaps in the Thue-Morse sequence and some variants 

      Brown, Shandy; Rampersad, Narad; Shallit, Jeffrey; Vasiga, Troy (EDP Sciences, 2006)
      We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are 2-regular. We also prove that changing any finite but nonzero number of bits in the ...
    • Binary Words Containing Infinitely Many Overlaps 

      Currie, James D.; Rampersad, Narad; Shallit, Jeffrey (The Electronic Journal of Combinatorics, 2006-09-22)
      We characterize the squares occurring in infinite overlap-free binary words and construct various α power-free binary words containing infinitely many overlaps.
    • Overlap-Free Words and Generalizations 

      Rampersad, Narad (University of WinnipegUniversity 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 ...
    • The Brachistochrone Problem: Mathematics for a Broad Audience via a Large Context Problem 

      Babb, Jeff; Currie, James (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 ...
    • 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 ...
    • Sliding Down Inclines with Fixed Descent Time: a Converse to Galileo's Law of Chords 

      Babb, Jeff (Canadian Mathematical Society, 2008-12)
    • 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.
    • 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 ...
    • Self-Complementary Hypergraphs 

      Gosselin, Shonda (University of OttawaUniversity of Ottawa and Carleton University (joint program), 2009)
      In this thesis, we survey the current research into self-complementary hypergraphs, and present several new results. We characterize the cycle type of the permutations on n elements with order equal to a power of 2 which ...
    • Vertex-transitive self-complementary uniform hypergraphs of prime order 

      Gosselin, Shonda (Discrete Mathematics, 2009-09)
      For an integer n and a prime p, let n(p)=max{i:pidividesn}. In this paper, we present a construction for vertex-transitive self-complementary k-uniform hypergraphs of order n for each integer n such that pn(p)≡1(mod2ℓ+1) ...
    • 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 ...
    • Generating self-complementary uniform hypergraphs 

      Gosselin, Shonda (Discrete Mathematics, 2010-02)
      In 2007, Szymanski and Wojda proved that for positive integers n; k with k less than n, a self-complementary k-uniform hypergraph of order n exists if and only if n/k is even. In this paper, we characterize the cycle type ...
    • Cyclically t-complementary uniform hypergraphs 

      Gosselin, Shonda (European Journal of Combinatorics, 2010-05)
      A cyclically t-complementary k-hypergraph is a k-uniform hypergraph with vertex set V and edge set E for which there exists a permutation 2 Sym.V/ such that the sets E; E ; E 2; : : : ; E t􀀀1 partition the set of all ...
    • 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.
    • Constructing Regular Self-complementary Uniform Hypergraphs 

      Gosselin, Shonda (Journal of Combinatorial Designs, 2011-02-17)
      In this paper, we examine the possible orders of t-subset-regular self-complementary k-uniform hypergraphs, which form examples of large sets of two isomorphic t-designs. We reformulate Khosrovshahi and Tayfeh-Rezaie's ...
    • Further applications of a power series method for pattern avoidance 

      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 ...
    • The minimal automaton recognizing mN in a linear numeration system 

      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 ...
    • The Aveline's Hole 9 Cranium: A Partial Solution to a Long Standing Enigma 

      Meiklejohn, Christopher; Schulting, Rick; Musgrave, Jonathan; Babb, Jeff; Higham, Thomas; Richards, David; Mullan, Graham (University of Bristol Spelaeological Society, 2012)
      Aveline's Hole is both one of the best-known sites with early human skeletal material in Britain and one of the most problematic in its history. First discovered and explored at the close of the 18th century, it yielded ...
    • 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 ...
    • Automaticity of Primitive Words and Irreducible Polynomials 

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