Department of Mathematics and Statistics
http://hdl.handle.net/10680/289
2020-06-03T11:57:10ZExtremal words in morphic subshifts
http://hdl.handle.net/10680/1763
Extremal words in morphic subshifts
Zamboni, Luca Q.; Saari, Kalle; Rampersad, Narad; Currie, James D.
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 x. In this
paper we consider the extremal words of morphic words. If x = g(f^\omega(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.
2014-01-22T00:00:00ZUnary patterns under permutations
http://hdl.handle.net/10680/1762
Unary patterns under permutations
Currie, James D.; Nowotka, Dirk; Manea, Florin; Reshadi, Kamellia
Thue characterized completely the avoidability of unary patterns. Adding function variables gives a general setting capturing avoidance of powers, avoidance of patterns with palindromes, avoidance of powers under coding, and other questions of recent interest. Unary patterns with permutations have been previously analysed only for lengths up to 3.
Consider a pattern $p=\pi_{i_1}(x)\ldots \pi_{i_r}(x)$, with $r\geq 4$, $x$ a word variable over an alphabet $\Sigma$ and $\pi_{i_j}$ function variables, to be replaced by morphic or antimorphic permutations of $\Sigma$. If $|\Sigma|\ge 3$, we show the existence of an infinite word avoiding all pattern instances having $|x|\geq 2$. If $|\Sigma|=3$ and all $\pi_{i_j}$ are powers of a single morphic or antimorphic $\pi$, the length restriction is removed. For the case when $\pi$ is morphic, the length dependency can be removed also for $|\Sigma|=4$, but not for $|\Sigma|=5$, as the pattern $x\pi^2(x)\pi^{56}(x)\pi^{33}(x)$ becomes unavoidable. Thus, in general, the restriction on $x$ cannot be removed, even for powers of morphic permutations. Moreover, we show that for every positive integer $n$ there exists $N$ and a pattern $\pi^{i_1}(x)\ldots \pi^{i_n}(x)$ which is unavoidable over all alphabets $\Sigma$ with at least $N$ letters and $\pi$ morphic or antimorphic permutation.
2018-06-04T00:00:00ZAvoiding three consecutive blocks of the same size and same sum
http://hdl.handle.net/10680/1761
Avoiding three consecutive blocks of the same size and same sum
Currie, James D.; Cassaigne, Julien; Shallit, Jeffrey O.; Schaeffer, Luke
We show that there exists an inﬁnite word over the alphabet {0,1,3,4} containing no three consecutive blocks of the same size and the same sum. This answers an open problem of Pirillo and Varricchio from1994.
2014-04-01T00:00:00ZGrowth rate of binary words avoiding xxxR
http://hdl.handle.net/10680/1760
Growth rate of binary words avoiding xxxR
Currie, James D.; Rampersad, Narad
Abstract
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 of the form n^{lg n+o(lg n)} on the number of
such words of length n, where lg n denotes the base-2 logarithm of n.
2016-01-01T00:00:00ZAbelian complexity of fixed point of morphism 0 -> 012, 1 -> 02, 2 -> 1
http://hdl.handle.net/10680/1759
Abelian complexity of fixed point of morphism 0 -> 012, 1 -> 02, 2 -> 1
Currie, James D.; Blanchet-Sadri, Francine; Fox, Nathan; Rampersad, Narad
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 inﬁnite ternary sequence appears a lot in the literature and ﬁnds applications in several ﬁelds such as combinatorics on words; for example, in pattern avoidance it is often used to construct inﬁnite words avoiding given patterns. It has been shown that the factor complexity of vtm, i.e., the number of factors of length n, is \Theta(n); in fact, it is bounded by 10/3 n for all n, and it reaches that bound precisely when n can be written as 3 times a power of 2. In this paper, we show that the abelian complexity of vtm, i.e., the number of Parikh vectors of length n, is O(logn) with constant approaching 3/4 (assuming base 2 logarithm), and it is \Omega(1) with constant 3 (and these are the best possible bounds). We also prove some results regarding factor indices in vtm.
2016-02-14T00:00:00ZBinary Words Avoiding xxRx and Strongly Unimodal Sequences
http://hdl.handle.net/10680/1758
Binary Words Avoiding xxRx and Strongly Unimodal Sequences
Currie, James D.; Rampersad, Narad
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 growth of the number
of binary words avoiding the pattern xxRx. Curiously, the analysis for xxRx is much
simpler than that for xxxR. We derive our results by giving a bijection between the
set of binary words avoiding xxRx and a class of sequences closely related to the class
of “strongly unimodal sequences”.
2015-09-14T00:00:00ZA family of formulas with reversal of high avoidability index
http://hdl.handle.net/10680/1755
A family of formulas with reversal of high avoidability index
Currie, James; Mol, Lucas; Rampersad, Narad
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 due to its size and the simple structure of its members. For each k ∈ {4,5}, there are several previously known avoidable formulas (without reversal) of avoidability index k, but they are small in number and they all have rather complex structure.
2017-01-01T00:00:00ZAvoidability index for binary patterns with reversal
http://hdl.handle.net/10680/1754
Avoidability index for binary patterns with reversal
Currie, James D.; Lafrance, Phillip
For every pattern p over the alphabet {x,x^R,y,y^R}, we specify the least k such that p is k-avoidable.
2017-01-01T00:00:00ZAttainable lengths for circular binary words avoiding k-powers
http://hdl.handle.net/10680/1752
Attainable lengths for circular binary words avoiding k-powers
Currie, James D.; Aberkane, Ali
We show that binary circular words of length n avoiding 7/3+ powers exist
for every sufficiently large n. This is not the case for binary circular words
avoiding k+ powers with k < 7/3
2005-01-01T00:00:00ZThe Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially
http://hdl.handle.net/10680/1751
The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially
Currie, James; Rampersad, Narad; Aberkane, Ali
We show that the number of ternary words of length n avoiding abelian cubes grows
faster than r^n, where r = 2^{1/24}
2004-06-19T00:00:00Z