Search
Now showing items 11-20 of 24
Shuffling and unshuffling
(Bulletin of the European Association for Theoretical Computer Science, 2012)
We consider various shuffling and unshuffling operations on languages and words, and examine their closure properties. Although the main goal is to provide some good and novel exercises and examples for undergraduate formal ...
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 ...
For each a > 2 there is an Infinite Binary Word with Critical Exponent a
(The Electronic Journal of Combinatorics, 2008-08-31)
The critical exponent of an infinite word w is the supremum of all rational numbers α such that w contains an α-power. We resolve an open question of Krieger and Shallit by showing that for each α>2 there is an infinite ...
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 ...
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 ...
Automaticity of Primitive Words and Irreducible Polynomials
(Discrete Mathematics and Theoretical Computer Science, 2013)
If L is a language, the automaticity function AL(n) (resp. NL(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all ...
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 ...
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 ...
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.