15 citations · 107 across the 77 of their papers we have counts for
6 papers · 1 filter
Dyck Words, Pattern Avoidance, and Automatic Sequences
Lucas Mol, Narad Rampersad, Jeffrey Shallit
We study various aspects of Dyck words appearing in binary sequences, where is treated as a left parenthesis and as a right parenthesis. We show that binary words that are…
Properties of a Ternary Infinite Word
James Currie, Pascal Ochem, Narad Rampersad +1
We study the properties of the ternary infinite word p = 012102101021012101021012 ... , that is, the fixed point of the map h:0->01, 1->21, 2->0. We determine its factor complexity…
An inequality for the number of periods in a word
Daniel Gabric, Narad Rampersad, Jeffrey Shallit
We prove an inequality for the number of periods in a word x in terms of the length of x and its initial critical exponent. Next, we characterize all periods of the length-n prefix…
Palindromic Ziv-Lempel and Crochemore Factorizations of -Bonacci Infinite Words
Marieh Jahannia, Morteza Mohammad-noori, Narad Rampersad +1
We introduce a variation of the Ziv-Lempel and Crochemore factorizations of words by requiring each factor to be a palindrome. We compute these factorizations for the Fibonacci wor…
Periodicity, repetitions, and orbits of an automatic sequence
Jean-Paul Allouche, Narad Rampersad, Jeffrey Shallit
We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidab…
Finding the growth rate of a regular language in polynomial time
Dalia Krieger, Narad Rampersad, Jeffrey Shallit
We give an O(n^3+n^2 t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. We also show that given a…