Browsing Department of Mathematics and Statistics by Issue Date
Now showing items 41-60 of 73
-
Square-free Words with Square-free Self-shuffles
(The Electronic Journal of Combinatorics, 2014-01-12)We answer a question of Harju: For every n ≥ 3 there is a square-free ternary word of length n with a square-free self-shuffle. -
Extremal words in morphic subshifts
(Elsevier, 2014-01-22)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 ... -
Abelian complexity of fixed point of morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1
(Integers, 2014-02-20)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 infinite ternary sequence appears a lot in the literature and finds ... -
Combinatorics and Algorithmics of Strings
(Dagstuhl Publishing, 2014-03-09)Strings (aka sequences or words) form the most basic and natural data structure. They occur whenever information is electronically transmitted (as bit streams), when natural language text is spoken or written down (as words ... -
Avoiding three consecutive blocks of the same size and same sum
(Association of Computing Machinery, 2014-04)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 from1994. -
Cubefree words with many squares
(Discrete Mathematics and Theoretical Computer Science, 2014-05-13)We construct infinite cubefree binary words containing exponentially many distinct squares of length n . We also show that for every positive integer n , there is a cubefree binary square of length 2n. -
Suffix conjugates for a class of morphic subshifts
(Cambridge University Press, 2015-09)Let A be a finite alphabet and f: A^* --> A^* be a morphism with an iterative fixed point f^\omega(\alpha), where \alpha{} is in A. Consider the subshift (X, T), where X is the shift orbit closure of f^\omega(\alpha) and ... -
Binary Words Avoiding xxRx and Strongly Unimodal Sequences
(2015-09-14)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 ... -
Avoiding approximate repetitions with respect to the longest common subsequence distance
(Mathematical Sciences Publishers, 2015-09-17)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 x x', where x and x' are close to being identical. ... -
Words with many palindrome pair factors
(The Electronic Journal of Combinatorics, 2015-10-30)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 ... -
A chrono-geographic look at Mesolithic burials: an initial study
(Landesamt für Denkmalpflege und Archäologie Sachsen-Anhalt, 2016)Over the past decade we have focused on two interrelated topics within Mesolithic burial studies, the relationship between burial number and burial date, and the chronology of Mesolithic sites with burials. Related to this ... -
Growth rate of binary words avoiding xxxR
(Elsevier, 2016-01)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 ... -
Avoidability index for binary patterns with reversal
(The Electronic Journal of Combinatorics, 2016-02-19)For every pattern p over the alphabet {x, x^R, y, y^R}, we specify the least k such that p is k-avoidable. -
A Ternary Square-free Sequence Avoiding Factors Equivalent to abcacba
(The Electronic Journal of Combinatorics, 2016-05-27)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 ... -
Avoidability index for binary patterns with reversal
(2017)For every pattern p over the alphabet {x,x^R,y,y^R}, we specify the least k such that p is k-avoidable. -
Skeleton Cave, Leigh Woods, Bristol
(University of Bristol Spelaeological Society, 2017)An account is given of the discovery and excavation of this small cave in the 1960s. It is recorded that archaeological finds were made, but of these, only a single human mandible can now be traced. Radiocarbon dating shows ... -
A family of formulas with reversal of high avoidability index
(World Scientific, 2017)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 ... -
On avoidability of formulas with reversal
(EDP Sciences, 2018-02-13)While a characterization of unavoidable formulas (without reversal) is well-known, little is known about the avoidability of formulas with reversal in general. In this article, we characterize the unavoidable formulas ... -
Cyclic Complexity of Some Infinite Words and Generalizations
(Integers, 2018-03)Cassaigne et al. introduced the cyclic complexity function c_x(n), which gives the number of cyclic conjugacy classes of length-n factors of a word x. We study the behavior of this function for the Fibonacci word f and the ...
