Recherche
Voici les éléments 11-20 de 84
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.
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 ...
The number of order–preserving maps of fences and crowns
(Springer, 1991-06)
We perform an exact enumeration of the order-preserving maps of fences (zig-zags) and crowns (cycles). From this we derive asymptotic results.
The metric dimension and metric independence of a graph
(The Charles Babbage Research Centre, 2001)
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 ...
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 ...
Unary patterns under permutations
(Elsevier, 2018-06-04)
Thue characterized completely the avoidability of unary patterns. Adding function variables gives a general setting capturing avoidance of powers, avoidance of patterns with palindromes, avoidance of powers under coding, ...
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.
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 ...
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 ...