BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We characterize exactly the lengths of binary circular words containing no squares other than 00, 11, and 0101. Key words: combinatorics on words, circular words, necklaces, square-free words, non-repetitive sequences
For a rational number r such that 1<r≤2, an undirected r-power is a word of the form xyx′, where the word x is nonempty, the word x′ is in {x,xR}, and we have ∣xyx′∣/∣xy∣=r. The undirected repetition threshold for k letters, denoted $\mbox{URT}(k)$, is the infimum of the set of all r such that undirected r-powers are avoidable on k letters. We first demonstrate that $\mbox{URT}(3)=\tfrac{7}{4}$. Then we show that $\mbox{URT}(k)\geq \tfrac{k-1}{k-2}$ for all k≥4. We conjecture that $\mbox{URT}(k)=\tfrac{k-1}{k-2}$ for all k≥4, and we confirm this conjecture for k∈{4,5,…,21}. We then consider related problems in pattern avoidance; in particular, we find the undirected avoidability index of every binary pattern. This is an extended version of a paper presented at WORDS 2019, and it contains new and improved results.
A word is level if each letter appears in it the same number of times, plus or minus 1. We give a complete characterization of the lengths for which level ternary circular square-free words exist. Key words: combinatorics on words, circular words, necklaces, square-free words, non-repetitive sequences
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: (1) characterize all the (two-way) infinite ternary square-free words avoiding letter pattern xyzxzyx (2) characterize the lexicographically least (one-way) infinite ternary square-free word avoiding letter pattern xyzxzyx (3) show that the number of ternary square-free words of length n avoiding letter pattern xyzxzyx grows exponentially with n.
Let G be the unit distance graph in the plane. A well-known problem in combinatorial geometry is that of determining the chromatic number of G. It is known that 4≤χ(G)≤7. The upper bound of 7 is obtained using tilings of the plane. The present paper studies two problems where we seek proper colourings of G, adding restrictions inspired by tilings: Let H(ε) be the graph whose vertices are the points of R2, with an edge between two points if their distance lies in the interval [1,1+ε]. We show that for small ε, 0<ε≤432−1, we have 6≤χ(H(ε))≤7. This improves the result of Exoo and Grytczuk et al. that 5≤χ(H(ε)) for small ε. Suppose that G is properly coloured, but so that two solidly coloured regions meet along a straight line in some neighbourhood. Then at least 5 colours must be used.
For every pattern p over the alphabet {x,y,xR,yR}, we specify the least k such that p is k-avoidable.
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 xxxR. 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 Cnlgn+c, where C, c are constants.
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 answer a question of Harju: An infinite square-free ternary word with an n-stem factorization exists for any n≥13. We show that there are uniform ternary morphisms of length k for every k≥23. This resolves almost completely a problem of the author and Rampersad.
We show that there exists an infinite 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 from 1994.
We show that the problem of whether the fixed point of a morphism avoids Abelian k-powers is decidable under rather general conditions
We give the avoidance indices (morphic and antimorphic) for all unary patterns with involution.
We give an effective characterization of the lexicographically least word in the orbit closure of the Rudin-Shapiro word w having a specified prefix. In particular, the lexicographically least word in the orbit closure of the Rudin-Shapiro word is 0w. This answers a question Allouche et al.
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.