BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Narad Rampersad appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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, critical exponent, and prove that it is 2-balanced. We compute its abelian complexity and determine the lengths of its bispecial factors. Finally, we give a characterization of p in terms of avoided factors.
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 of a characteristic Sturmian word in terms of the lazy Ostrowski representation of n, and use this result to show that our inequality is tight for infinitely many words x. We propose two related measures of periodicity for infinite words. Finally, we also consider special cases where x is overlap-free or squarefree.
We study the following natural variation on the classical universality problem: given a language $L(M)$ represented by $M$ (e.g., a DFA/RE/NFA/PDA), does there exist an integer $\ell \geq 0$ such that $Σ^\ell \subseteq L(M)$? In the case of an NFA, we show that this problem is NEXPTIME-complete, and the smallest such $\ell$ can be doubly exponential in the number of states. This particular case was formulated as an open problem in 2009, and our solution uses a novel and involved construction. In the case of a PDA, we show that it is recursively unsolvable, while the smallest such $\ell$ is not bounded by any computable function of the number of states. In the case of a DFA, we show that the problem is NP-complete, and $e^{\sqrt{n \log n} (1+o(1))}$ is an asymptotically tight upper bound for the smallest such $\ell$, where $n$ is the number of states. Finally, we prove that in all these cases, the problem becomes computationally easier when the length $\ell$ is also given in binary in the input: it is polynomially solvable for a DFA, PSPACE-complete for an NFA, and co-NEXPTIME-complete for a PDA.
An overlap-free (or $β$-free) word $w$ over a fixed alphabet $Σ$ is extremal if every word obtained from $w$ by inserting a single letter from $Σ$ at any position contains an overlap (or a factor of exponent at least $β$, respectively). We find all lengths which admit an extremal overlap-free binary word. For every extended real number $β$ such that $2^+\leqβ\leq 8/3$, we show that there are arbitrarily long extremal $β$-free binary words.
A square-free word $w$ over a fixed alphabet $Σ$ is extremal if every word obtained from $w$ by inserting a single letter from $Σ$ (at any position) contains a square. Grytczuk et al. recently introduced the concept of extremal square-free word, and demonstrated that there are arbitrarily long extremal square-free ternary words. We find all lengths which admit an extremal square-free ternary word. In particular, we show that there is an extremal square-free ternary word of every sufficiently large length. We also solve the analogous problem for circular words.
We give a partial answer to a problem of Harju by constructing an infinite ternary squarefree word $w$ with the property that for every $k \geq 3312$ there is an interior length-$k$ factor of $w$ that can be deleted while still preserving squarefreeness. We also examine Thue's famous squarefree word (generated by iterating the map $0 \to 012$, $1 \to 02$, $2 \to 1$) and characterize the positions $i$ for which deleting the symbol appearing at position $i$ preserves squarefreeness.
The initial non-repetitive complexity function of an infinite word x (first defined by Moothathu) is the function of n that counts the number of distinct factors of length n that appear at the beginning of x prior to the first repetition of a length-n factor. We examine general properties of the initial non-repetitive complexity function, as well as obtain formulas for the initial non-repetitive complexity of the Thue-Morse word, the Fibonacci word and the Tribonacci word.
We characterize the finite sets S of words such that that the iterated shuffle of S is co-finite and we give some bounds on the length of a longest word not in the iterated shuffle of S.
In previous work, Currie and Rampersad showed that the growth of the number of binary words avoiding the pattern xxx^R was intermediate between polynomial and exponential. We now show that the same holds for the growth of the number of binary words avoiding the pattern xx^Rx. Curiously, the analysis for xx^Rx is much simpler than that for xxx^R. We derive our results by giving a bijection between the set of binary words avoiding xx^Rx and a class of sequences closely related to the class of "strongly unimodal sequences."
Consider the set of those binary words with no non-empty 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 paper, we demonstrate the existence of upper and lower bounds on the number of such words of length $n$, where each of these bounds is asymptotically equivalent to a (different) function of the form $Cn^{\lg n+c}$, where $C$, $c$ are constants.
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 has this property, but this does not characterize the class of Sturmian words. We also show that the Thue-Morse word does not have this property. We investigate finite words with the maximal number of distinct palindrome pair factors and characterize the binary words that are not palindrome pairs but have the property that every proper factor is a palindrome pair.
We introduce the sequence $(i_n)_{n \geq 0}$ defined by $i_n = (-1)^{inv_2(n)}$, where $inv_2(n)$ denotes the number of inversions (i.e., occurrences of 10 as a scattered subsequence) in the binary representation of n. We show that this sequence has many similarities to the classical Rudin-Shapiro sequence. In particular, if S(N) denotes the N-th partial sum of the sequence $(i_n)_{n \geq 0}$, we show that $S(N) = G(\log_4 N)\sqrt{N}$, where G is a certain function that oscillates periodically between $\sqrt{3}/3$ and $\sqrt{2}$.
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 xx', where x and x' are close to being identical. In their work, they measured the similarity of x and x' using either the Hamming distance or the edit distance. In this paper, we show the existence of words avoiding approximate repetitions, where the measure of similarity between adjacent factors is based on the length of the longest common subsequence. Our principal technique is the so-called "entropy compression" method, which has its origins in Moser and Tardos's algorithmic version of the Lovasz local lemma.
In 2008, Kurosaki gave a new construction of a (bi-)infinite squarefree word over three letters. We show that in fact Kurosaki's word avoids 7/4+-powers, which, as shown by Dejean, is optimal over a 3-letter alphabet.
Given an infinite word X over an alphabet A a letter b occurring in X, and a total order σon A, we call the smallest word with respect to σstarting with b in the shift orbit closure of X an extremal word of X. In this paper we consider the extremal words of morphic words. If X = g(f^ω(a)) for some morphisms f and g, we give two simple conditions on f and g that guarantees that all extremal words are morphic. This happens, in particular, when X is a primitive morphic or a binary pure morphic word. Our techniques provide characterizations of the extremal words of the Period-doubling word and the Chacon word and give a new proof of the form of the lexicographically least word in the shift orbit closure of the Rudin-Shapiro word.
Let A be a finite alphabet and f: A^* --> A^* be a morphism with an iterative fixed point f^ω(α), where α is in A. Consider the subshift (X, T), where X is the shift orbit closure of f^ω(α) and T: X --> X is the shift map. Let S be a finite alphabet that is in bijective correspondence via a mapping c with the set of nonempty suffixes of the images f(a) for a in A. Let calS be a subset S^N be the set of infinite words s = (s_n)_{n\geq 0} such that π(s):= c(s_0)f(c(s_1)) f^2(c(s_2))... is in X. We show that if f is primitive and f(A) is a suffix code, then there exists a mapping H: calS --> calS such that (calS, H) is a topological dynamical system and π: (calS, H) --> (X, T) is a conjugacy; we call (calS, H) the suffix conjugate of (X, T). In the special case when f is the Fibonacci or the Thue-Morse morphism, we show that the subshift (calS, T) is sofic, that is, the language of calS is regular.
We show that the abelian complexity function of the ordinary paperfolding word is a 2-regular sequence.
We show that various aspects of k-automatic sequences -- such as having an unbordered factor of length n -- are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.
We prove a Fife-like characterization of the infinite binary (7/3)-power-free words, by giving a finite automaton of 15 states that encodes all such words. As a consequence, we characterize all such words that are 2-automatic.
We show that the problem of whether the fixed point of a morphism avoids Abelian $k$-powers is decidable under rather general conditions
We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free. We can determine whether a word is Abelian primitive in linear time. Also different from classical primitive words, we find that a word may have more than one Abelian root. We also consider enumeration problems and the relation to the theory of codes.
A language L is closed if L = L*. We consider an operation on closed languages, L-*, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L-* is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free.
We prove that the subsets of N^d 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.
Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m >= 2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of the multiples of m in the Fibonacci system is exactly 2m^2.
A set $X\subseteq\mathbb N$ is S-recognizable for an abstract numeration system S if the set $\rep_S(X)$ of its representations is accepted by a finite automaton. We show that the growth function of an S-recognizable set is always either $Θ((\log(n))^{c-df}n^f)$ where $c,d\in\mathbb N$ and $f\ge 1$, or $Θ(n^r θ^{Θ(n^q)})$, where $r,q\in\mathbb Q$ with $q\le 1$. If the number of words of length n in the numeration language is bounded by a polynomial, then the growth function of an S-recognizable set is $Θ(n^r)$, where $r\in \mathbb Q$ with $r\ge 1$. Furthermore, for every $r\in \mathbb Q$ with $r\ge 1$, we can provide an abstract numeration system S built on a polynomial language and an S-recognizable set such that the growth function of X is $Θ(n^r)$. For all positive integers k and l, we can also provide an abstract numeration system S built on a exponential language and an S-recognizable set such that the growth function of X is $Θ((\log(n))^k n^l)$.