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
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 ...
6
votes
1
answer
279
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
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
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
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
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
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
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
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
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
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
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,074
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
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
-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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
1
answer
122
views
Partition theorems for located words
In this paper Bergelson, Blass, and Hindman prove the following
Theorem 1.2 Let $W(\Sigma; v)$ be colored with finitely may colors and let $\bar s$ be an infinite sequence from $W(\Sigma; v)$. ...
2
votes
1
answer
238
views
Unique(ish) infinite string avoiding a set of patterns
Let $\Sigma$ be a finite alphabet of size at least 2. A (possibly infinite) string $s$ over alphabet $\Sigma$ encounters a pattern $p \in \mathbb{N}^*$ iff there is a non-erasing morphism $f: \mathbb{...
- 5,590
4
votes
1
answer
157
views
Subshifts with a free semigroup
Let $X$ be a subshift on a finite alphabet. I'm interested in the following property: there exist words $s,t\in\mathcal L(X)$ (the language of $X$) such that $\{s,t\}^*\subset \mathcal L(X)$. That is, ...
- 2,135
1
vote
0
answers
45
views
Latent Dirichlet Allocation on Contrived Data
I am doing a project that seems like it might be susceptible to Latent Dirichlet Allocation. However, my data is highly contrived (both in test cases and use cases) and my "words" don't come close to ...
- 612
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
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
3
votes
0
answers
285
views
Cayley Graphs and Cyclically reduced words [closed]
Let $G$ be a finite group and $S$ be a symmetric generating set for $G$. (EDIT: Assume $S$ does not contain involutions!) Cyclically reduced words can be thought of as minimal length representatives ...
- 949
4
votes
1
answer
164
views
Covering sequences of words
(If anyone has a better title please change it!)
Given two finite words $v,w$ in the alphabet $\{a,b\}$, define the $v$-proportion of $w$ to be the largest number of letters in $w$ which can be ...
- 743
0
votes
1
answer
159
views
How many words are there such that some word $X$ is subsequence of them?
Let's define subsequence of the word as part of the word created by deleting some of its letters, for example aetics is a subsequence of mathematics.
QUESTION.
Given a $3$-letter word (let's call it ...
5
votes
0
answers
1k
views
The functional equation $f(x) = qx + qxf(x) - f(x^2)$
A word (i.e., ordered string of letters) is bifix-free provided it has no proper initial string and terminal string that are identical. For example, the word $ingratiating$ has bifix $ing$, but the ...
- 399
17
votes
0
answers
536
views
Question about combinatorics on words
Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$.
Question: Is there an algorithm to check if for some $m,k$...
user6976
5
votes
1
answer
399
views
Number of Lyndon words of given weight
Consider the alphabet consisting of two letters $a$ and $b$, and put the lexicographic order in which $a<b$.
We say that a non-empty word $w$ in this alphabet is a Lyndon word if, for any non-...
- 51
3
votes
1
answer
282
views
Longest runs and concentration of measure
Consider the longest runs $\ell_\sigma(x)$ of the pattern $\sigma$ for $\sigma\in \{0, 1, 01, 10, 001,\dots\}$ etc. in a binary sequence $x=x_1\dots x_n$.
For example, $\ell_{001}(0001110010011001)=2$...
- 24.8k