Questions tagged [combinatorics-on-words]
A branch of combinatorics that focuses on the study of words and formal languages
104 questions
4
votes
1
answer
189
views
Equation in the conjugacy class of a free group
I will pose the question in the form in which it originally appeared to me:
Let $a,b,c,d$ be different letters in a finite alphabet $\mathcal{Z}$. Let $Q$ and $R$ be finite words with letters from $\...
- 111
6
votes
1
answer
388
views
What is the max number of self-segregating words of length n?
A set of words S is called self-segregating if you don't need whitespaces to read them. It means that for any two words from S no new words from S arise between them.
For example the set ab, bc, ac, ...
- 125
10
votes
1
answer
467
views
Elegant proof for $xy < yx \Leftrightarrow x^\mathbb{N} < y^\mathbb{N}$
Let $x, y$ be finite words over totally ordered alphabet and $<$ denote the lexicographical order, i.e for two not necessarily finite words we say $x < y$ iff one of the following holds
There ...
- 163
1
vote
0
answers
169
views
A function $g : \{0,1\}^m \to \{0,1\}^{4m}$ such that the “circular discrepancy” between $g(x_1)$ and $g(x_2)$ is $\geq m$ for any $x_1 \neq x_2$
In this question, the term “word” implies a binary word, i.e. a sequence of bits.
Let $W(x)$ denote the number of non-zero bits in a word $x$.
Assuming that $x$ is an $s$-bit word and $0 \le k < s$,...
- 959
6
votes
1
answer
280
views
A Sauer-Shelah-like lermma for prefix tree
I proved a variant of the Sauer-Shelah lemma and I was wondering if something like that is already known.
Let $S \subseteq \{0,1\}^n $. We say that a set of coordinates $K \subseteq [n]$ is shattered ...
- 419
2
votes
0
answers
101
views
Combinatorics on non-associative words
In my P.h.d research, I deal (among other things) with non-associative words, which we call monomials, and we need to consider two types of operations with these monomials.
The first one is simply ...
2
votes
1
answer
168
views
Is there an efficient algorithm that allows to construct a binary word with particular properties related to its horizontal and vertical “subwords”?
Let $w$ denote an $mn$-bit word (i.e. a binary word of length $mn$). Assuming that $b_{i,j}$ denote individual bits, we can represent $w$ in the “rectangular” form as follows:
$$\begin{array}{l}
b_{1....
- 959
4
votes
1
answer
260
views
Word combinatorics terminology question
I'm looking for the name of what I suspect must be a standard property, and also for a possible statement about that property.
First the property: $W=a_0\ldots a_{n-1}$ has this property if for all $1\...
- 23.2k
4
votes
1
answer
245
views
Hausdorff dimension and critical exponent of words
What is the Hausdorff dimension of the subset $S_c \subset [0,1]$ of points such that the critical exponent of their binary expansion is $c$? It's clear that $\dim_H S_{\infty}=1$, but what can be ...
- 4,459
7
votes
2
answers
319
views
Is there an efficient generalized algorithm to find at least one binary word with the maximum rotational imbalance and the full $\{0, 1\}$-balance?
Assuming that $x$ is a sequence of $l$ bits (i.e. a binary word of length $l$) and $0 \le m < l$, let $R(x, m)$ denote the result of the left bitwise rotation (i.e. the left circular shift) of $x$ ...
- 959
19
votes
6
answers
3k
views
Subwords of the Fibonacci word
The Fibonacci word is the limit of the sequence of words starting with "$0$" and satisfying rules $0 \to 01, 1 \to 0$. It's equivalent to have initial conditions $S_0 = 0, S_1 = 01$ and ...
- 22.8k
3
votes
1
answer
349
views
Is the number of words finite, when you don't know how to count?
This question is inspired by this one:
Can you do math without knowing how to count?
Let $M_2$ be the set of words constructed by concatenation of the letters $a_1$ and $a_2$, with :
(*) : for any $x$ ...
- 4,073
33
votes
0
answers
2k
views
The easily bored sequence
If we want to compare the repetitiveness of two finite words, it looks reasonable, first of all, to consider more repetitive the word repeating more times one of its factors, and secondarily to ...
- 4,459
21
votes
6
answers
2k
views
Are there uncountably many cube-free infinite binary words?
In Cube-free infinite binary words it was established that there are infinitely many cube-free infinite binary words (see the earlier question for definitions of terms). The construction given in ...
- 39.9k
19
votes
3
answers
1k
views
What is the fairest order for stage-striking (and is it the Thue-Morse sequence)?
Here's a fair-sequencing problem that doesn't quite match the usual fair-division problems. I think that, like those, the answer should also be the Thue-Morse sequence ("balanced alternation"), ...
- 2,585
3
votes
0
answers
95
views
What is the minimum length of a $k$-permutation-avoiding word on $n$ letters?
Let $w$ be a word over the alphabet $[n] := \{1, \dots, n\}$. For a fixed $S \subseteq [n]$, let $w_S$ be the word obtained from $w$ by deleting all entries not in $S$, then removing (all but one ...
- 183
19
votes
5
answers
1k
views
Three-halves-free words (analogous to square-free)
A square-free word
is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any
consecutive sequence of symbols in the string.
For alphabets of two symbols, the longest square-free ...
- 151k
4
votes
2
answers
259
views
Binary words that are nonconstant on long arithmetic progressions
Let $w=x_0 x_1 x_2 \ldots$ be an infinite word, where each $x_i\in \{0,1\}$. For each positive integer $k$ (thought of as the jump size of an arithmetic progression) and each residue $0\leq a \leq k-...
- 18.7k
1
vote
1
answer
121
views
Is there an efficient generalized algorithm to generate a set of binary words satisfying a particular cross-correlation property?
In this question, the term “word” implies a binary word, i.e. a sequence of bits.
Let $W(w)$ denote the number of non-zero bits in a word $w$.
Assuming that $l \geq 2$ is even, an $l$-bit word $w$ is ...
- 959
5
votes
1
answer
123
views
Algorithms to factorize words into product of powers
I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references.
Let $A$ be a finite set of symbols, are there ...
- 477
12
votes
1
answer
427
views
Subwords of the infinite Fibonacci word
Let $W = 01001010010010 \ldots$ be the infinite Fibonacci word, A003849 in the OEIS. Let $B(m)$ be the set of $m+1$ subwords of $W$ that have length $m$, and for each such subword $u$, let $p(u)$ be ...
- 479
3
votes
1
answer
261
views
Words with critical exponent $< \frac 73$
In a comment made by Gjergji Zaimi to this older question, it is conjectured that $\frac 73$ is the threshold separating countability and uncountability of the sets of infinite binary words having a ...
- 4,459
9
votes
2
answers
383
views
A cubefree-preserving morphism from 5 to 2?
A word is cubefree if it cannot be written as $xyyyz$ where $y$ has positive length.
Let $h$ be the morphism from $\{0,1,2,3,4\}^*$ to $\{0,1\}^*$ given for words of length 1 as follows ($a\to h(a)$):...
- 24.8k
5
votes
1
answer
310
views
In the Oldenburger-Kolakoski sequence, is #1s = #2s infinitely many times?
The Oldenburger-Kolakoski sequence, $OK$, is the unique sequence of $1$s and $2$s that starts with $1$ and is its own runlength sequence:
$$OK = (1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,\ldots).$...
- 479
2
votes
3
answers
639
views
The critical exponent function
It is a known fact [1] that, for every $c\in (1,\infty]$, it is possible to find a finite alphabet $\mathcal{A}$ and a word $w\in \mathcal{A}^\omega$ such that $w$ has critical exponent $c$. It looks ...
- 4,459
2
votes
1
answer
121
views
Binary words starting with arbitrarily long squares
What is the measure of the following set of infinite binary words?
$S=\{w\in\{0,1\}^\omega\ \text{such that},\ \text{for every}\ N\in\mathbb{N},\, w\ \text{has a prefix of the form}\ pp\ \text{with}\ ...
- 4,459
32
votes
3
answers
2k
views
"Nyldon words": understanding a class of words factorizing the free monoid increasingly
BACKGROUND.
Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner'...
- 33.8k
6
votes
1
answer
193
views
Is there a prefix-continuous bijection between finite words and eventually zero words?
Let
$$ X = \{x \in \{0,1\}^{\omega} \;|\; \exists m: \forall i \geq m: x_i = 0\} $$
(one-way infinite eventually zero words). Let $\{0,1\}^*$ denote the finite (not necessarily nonempty) words over $\{...
- 6,652
2
votes
1
answer
133
views
What is the cardinality of the set of Dyck natural numbers of semilength $k$?
In arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I show that there is a 1:1 correspondence between $\mathbb{N} = \{0,1,2,3,4,\ldots\}$ and $\mathcal{D}_{r_{\...
- 129
9
votes
0
answers
467
views
Measuring the randomness of texts
The question concerns statistic properties of random words in a finite alphabet $A$.
By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$.
...
- 42k
5
votes
0
answers
113
views
Computability of the "free envelope rank" of an endomorphism of a free group
Let $F$ be a free group freely generated by the finite set $S$ and $\sigma\colon F\to F$ be a group morphism. We define the free envelope rank of $\sigma$, written $r(\sigma)$, as the smallest $k$ for ...
- 151
-1
votes
1
answer
125
views
Prove using Dyck naturals: for $n \in \mathbb{N}_{+}$ and big enough $k \in \mathbb{N}_{+}$, $p_{k-1} < \cdots < np_{k-a_{n}}$ (a is A073093)
While conducting research in connection with arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I noticed certain interesting patterns, one of which inspired the ...
- 129
20
votes
4
answers
3k
views
Cube-free infinite binary words
A word $y$ is a subword of $w$ if there exist words $x$ and $z$ (possibly empty) such that $w=xyz$. Thus, $01$ is a subword of $0110$, but $00$ is not a subword of $0110$. I'm interested in right-...
- 1,329
15
votes
7
answers
1k
views
Two questions from combinatorics on words
Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...
- 2,135
7
votes
1
answer
245
views
Is the density of 1's in the Fibonacci word uniform?
The Fibonacci word is the limit of the sequence of words starting with $0$ and satisfying rules $0 \to 01, 1 \to 0$. Equivalently, it is obtained from the recursion $S_n= S_{n-1}S_{n-2}$ under ...
- 785
5
votes
2
answers
203
views
Existence of an infinite word with a predetermined asymptotic for the word complexity
Let $w$ be an infinite binary word, for example: $$1010100001 0010011000 0001001110 0101011011 \dots$$
Let $N_w(k)$ be the set of distinct subwords of $w$ of length $k$, and $n_w(k)$ the cardinal of ...
6
votes
2
answers
319
views
Uniqueness of "Limit" of Cyclic Binary Strings
Set-up: By abuse, let $\sigma$ represent both the left shift operator on infinite bi-infinite strings and the cyclic left shift operator on finite strings. (Thus, for example, $\sigma(...01\bar{0}10......
- 115
1
vote
0
answers
78
views
Words with finite critical exponent
Let $\mathcal{A}$ be a finite set. Is there a nice characterization of the subset of $S\subset \mathcal{A}^\omega$ such that every $w\in S$ has finite critical exponent? Of course $S$ has measure zero ...
- 4,459
15
votes
1
answer
558
views
Combinatorics of palindromic decompositions
This is sort of a companion to my question Number of trivializations of a trivial word in the free group (which in turn is motivated by my earlier question here). It turns out that that question may ...
- 18.4k
2
votes
0
answers
189
views
$V$-like actions of $V$
This continues my question about prefix-continuous bijections (since the answer was "yes").
Notation and conventions: Let $A$ be a finite alphabet and $L \subset A^*$ a language. Let $G$ be a group. ...
- 6,652
4
votes
0
answers
145
views
Words that give rise to an enumeration of elements of the symmetric group
Let $\mathbb{S}_m$ be the symmetric group on $m$ letters. Let $n=m-1$. Let $\mathbf{w}=a_1\cdots a_r$ be a word on the alphabet $\{1,\ldots,n\}$. We say that $\mathbf{w}$ gives rise to an enumeration ...
- 1,066
4
votes
1
answer
231
views
Conjecture about infinite word
Let $w=a_1a_2a_3...$ be an infinite word over a finite alphabet and $\epsilon>0$. Do there exist integers $n,k$ such that $\frac{d(a_1a_2...a_n,a_{k+1}a_{k+2}...a_{k+n})}{n}<\epsilon$ ?
($d(u,v)$...
user136612
10
votes
0
answers
399
views
Words and ranks
Let me state two problems that look very much alike. The first one can be solved putting together answers that different people have given to some questions I asked here a few weeks ago. The second ...
- 20.2k
8
votes
1
answer
213
views
Minimum number of permutations of $\{1,\ldots, n\}$ that together contain every $k$-subpermutation
Define a $k$-permutation of $\{1,\ldots, n\}$ to be a word $\tau_1 \ldots \tau_k$ such that $\{\tau_1,\ldots,\tau_k\}$ is a $k$-subset of $\{1,\ldots, n\}$. Thus an $n$-permutation of $\{1,\ldots, n\}$...
- 11.2k
1
vote
1
answer
110
views
Cliques in overlap graphs for words
Let $\Sigma$ be a finite alphabet, and consider the free monoid $\Sigma^*$. Given $w, w' \in \Sigma^*$ we say that $w$ overlaps $w'$ if there exist non-empty words $u, v, u'$ such that $w = uv$ and $w'...
- 435
11
votes
1
answer
328
views
Unique words in dihedral groups
Suppose $x$ is a word over the alphabet $\{0,1\}$.
Let $a$, $b$ be elements of the group Dih$_k$ for some $k$.
Let $\varphi=\varphi_{a,b,k}$ be the map from words over $\{0,1\}$ to elements of the ...
- 24.8k
17
votes
3
answers
736
views
Probability that a word in the free group becomes (much) shorter?
Let $w$ be a word of length $2\ell$ chosen at random on the alphabet $\{x_1,x_1^{-1},x_2,x_2^{-1},\dotsc,x_k,x_k^{-1}\}$. By the reduction $\rho(w)$ I mean what you obtain by deleting substrings of ...
- 20.2k
12
votes
1
answer
544
views
Is the set of cube-free binary sequences perfect?
This question is inspired by this one. In that thread, it's established that there are uncountably many cube-free infinite binary strings (where $x \in 2^{\omega}$ is cube-free iff $\forall \sigma \...
- 3,992
24
votes
3
answers
865
views
an operation on binary strings
Recently, as part of some joint research, Tom Roby was led to a curious operation on strings of L's and R's which he calls "bounce-reading": We start by reading the string at the left. When the ...
- 19.7k
12
votes
1
answer
415
views
"Bisecting" a free subgroup with respect to word length
My broad question is regarding the lengths of (reduced) words in a subgroup of a free group.
As motivation, consider the free group $Gp(S)$ where $|S|=n$, that is, a free group of rank $n$. Let $S=\{...
- 949