Browsing by Author "Rampersad, Narad"
Now showing items 120 of 25

Abelian complexity of fixed point of morphism 0 > 012, 1 > 02, 2 > 1
Currie, James D.; BlanchetSadri, Francine; Fox, Nathan; Rampersad, Narad (20160214)We study the combinatorics of vtm, a variant of the ThueMorse word generated by the nonuniform morphism 0 > 012,1 > 02,2 > 1 starting with 0. This inﬁnite ternary sequence appears a lot in the literature and ﬁnds ... 
Abelian complexity of fixed point of morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1
BlanchetSadri, F.; Currie, James D.; Rampersad, Narad; Fox, Nathan (Integers, 20140220)We study the combinatorics of vtm, a variant of the ThueMorse word generated by the nonuniform morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1 starting with 0. This infinite ternary sequence appears a lot in the literature and finds ... 
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. nondeterministic) finite automaton that accepts a language that agrees with L on all ... 
Avoiding approximate repetitions with respect to the longest common subsequence distance
Camungol, Serina; Rampersad, Narad (Mathematical Sciences Publishers, 20150917)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. ... 
Binary Words Avoiding xxRx and Strongly Unimodal Sequences
Currie, James D.; Rampersad, Narad (20150914)In previous work, Currie and Rampersad showed that the growth of the number of binary words avoiding the pattern xxxR was intermediate between polynomial and exponential. We now show that the same result holds for the ... 
Binary Words Containing Infinitely Many Overlaps
Currie, James D.; Rampersad, Narad; Shallit, Jeffrey (The Electronic Journal of Combinatorics, 20060922)We characterize the squares occurring in infinite overlapfree binary words and construct various α powerfree binary words containing infinitely many overlaps. 
Cubefree words with many squares
Currie, James D.; Rampersad, Narad (Discrete Mathematics and Theoretical Computer Science, 20140513)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. 
Cyclic Complexity of Some Infinite Words and Generalizations
Krawchuk, Colin; Rampersad, Narad (Integers, 201803)Cassaigne et al. introduced the cyclic complexity function c_x(n), which gives the number of cyclic conjugacy classes of lengthn factors of a word x. We study the behavior of this function for the Fibonacci word f and the ... 
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. 
Extremal words in morphic subshifts
Zamboni, Luca Q.; Saari, Kalle; Rampersad, Narad; Currie, James D. (Elsevier, 20140122)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, 20080831)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 ... 
Further applications of a power series method for pattern avoidance
Rampersad, Narad (The Electronic Journal of Combinatorics, 20110621)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 nonerasing morphism h from ∆* to ∑* such that h(p) = x. Bell and Goh have recently ... 
Growth rate of binary words avoiding xxxR
Currie, James D.; Rampersad, Narad (Elsevier, 201601)Abstract Consider the set of those binary words with no nonempty 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 ... 
Introduction: Special volume in honor of Jeffrey Shallit on the occasion of his 60th birthday
Rampersad, Narad (Integers, 201803) 
The minimal automaton recognizing mN in a linear numeration system
Charlier, Émilie; Rampersad, Narad; Rigo, Michel; Waxweiler, Laurent (Integers, 20111202)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 ... 
Multidimensional 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 Srecognizable for all abstract numeration systems S are exactly the 1recognizable sets. This generalizes a result of Lecomte and Rigo in the onedimensional setting. 
The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially
Currie, James; Rampersad, Narad; Aberkane, Ali (20040619)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, 20180213)While a characterization of unavoidable formulas (without reversal) is wellknown, little is known about the avoidability of formulas with reversal in general. In this article, we characterize the unavoidable formulas ...