Department of Mathematics and Statistics
http://hdl.handle.net/10680/289
2019-12-11T10:46:14ZAbelian 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 ternary square-free sequence avoiding factors equivalent to abcacba
http://hdl.handle.net/10680/1756
A ternary square-free sequence avoiding factors equivalent to abcacba
Currie, James D.
We solve a problem of Petrova, finalizing the classification of letter patterns avoidable by ternary square-free words; we show that there is a ternary square-free word avoiding letter pattern xyzxzyx. In fact, we
-characterize all the (two-way) infinite ternary square-free words avoiding letter pattern xyzxzyx
-characterize the lexicographically least (one-way) infinite ternary square-free word avoiding letter pattern xyzxzyx
-show that the number of ternary square-free words of length n avoiding letter pattern xyzxzyx grows exponentially with
n.
2016-05-27T00: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:00ZBinary words containing infinitely many overlaps
http://hdl.handle.net/10680/1753
Binary words containing infinitely many overlaps
Currie, James D.; Rampersad, Narad; Shallit, Jeffrey
We characterize the squares occurring in infinite overlap-free binary words and construct various \alpha power-free binary words containing infinitely many overlaps.
2006-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:00ZThe metric dimension and metric independence of a graph
http://hdl.handle.net/10680/1746
The metric dimension and metric independence of a graph
Currie, James; Oellerman, Ortrud R.
A vertex x of a graph G resolves two vertices u and v of G if the
distance from x to u does not equal the distance from x to v. A set
S of vertices of G is a resolving set for G if every two distinct vertices
of G are resolved by some vertex of S. The minimum cardinality of a
resolving set for G is called the metric dimension of G. The problem of
nding the metric dimension of a graph is formulated as an integer pro-
gramming problem. It is shown how a relaxation of this problem leads
to a linear programming problem and hence to a fractional version of
the metric dimension of a graph. The linear programming dual of this
problem is considered and the solution to the corresponding integer
programming problem is called the metric independence of the graph.
It is shown that the problem of deciding whether, for a given graph
G, the metric dimension of G equals its metric independence is NP-
complete. Trees with equal metric dimension and metric independence
are characterized. The metric independence number is established for
various classes of graphs.
2001-01-01T00:00:00ZSliding Down Inclines with Fixed Descent Time: a Converse to Galileo's Law of Chords
http://hdl.handle.net/10680/1741
Sliding Down Inclines with Fixed Descent Time: a Converse to Galileo's Law of Chords
Babb, Jeff
2008-12-01T00:00:00Z