Search
Now showing items 11-20 of 24
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. ...
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 ...
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 ...
The minimal automaton recognizing mN in a linear numeration system
(Integers, 2011-12-02)
We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component ...
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 ...
Multi-dimensional sets recognizable in all abstract numeration systems
(EDP Sciences, 2011)
We prove that the subsets of Nd that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.
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 ...
Overlap-Free Words and Generalizations
(University of Winnipeg, 2007)
The study of combinatorics on words dates back at least to the beginning of the
20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains ...