Questions tagged [combinatorics-on-words]
A branch of combinatorics that focuses on the study of words and formal languages
100
questions
2
votes
0
answers
55
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
226
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
152
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....
- 899
3
votes
0
answers
64
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
238
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\...
- 22.2k
1
vote
1
answer
107
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 ...
- 899
7
votes
2
answers
287
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$ ...
- 899
3
votes
1
answer
247
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,096
5
votes
1
answer
108
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
250
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).$...
- 469
5
votes
0
answers
106
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 ...
- 141
2
votes
1
answer
331
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$ ...
- 3,355
4
votes
1
answer
223
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,096
2
votes
1
answer
125
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
119
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
74
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,096
12
votes
1
answer
392
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 ...
- 469
2
votes
1
answer
115
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,096
32
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,096
2
votes
3
answers
627
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,096
4
votes
2
answers
243
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-...
- 17.3k
10
votes
0
answers
390
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$.
...
- 38.7k
4
votes
0
answers
131
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 ...
- 962
2
votes
0
answers
180
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. ...
- 5,790
6
votes
1
answer
183
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 $\{...
- 5,790
9
votes
2
answers
379
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.1k
1
vote
1
answer
99
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
389
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 ...
- 18.6k
6
votes
2
answers
304
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
223
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
215
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 ...
- 755
8
votes
1
answer
200
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\}$...
- 10.5k
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,565
3
votes
1
answer
118
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
209
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,302
4
votes
1
answer
138
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,448
1
vote
0
answers
38
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 ...
- 602
12
votes
1
answer
391
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=\{...
- 939
11
votes
1
answer
315
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.1k
3
votes
0
answers
268
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 ...
- 939
4
votes
1
answer
159
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 ...
- 681
0
votes
1
answer
158
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 ...
- 389
17
votes
0
answers
522
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
358
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
269
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.1k
0
votes
0
answers
180
views
Sum of unit vectors always has a binary span after constrained permutations
Conjecture:
Let $e_1 = (1,0,\ldots,0), \ldots , e_{m_1+m_2} = (0,\ldots,0,1)$ be the unit vectors of the standard basis $E$ of $\mathbb{R}^{m_1+m_2}$.
An enumeration $ E \cup -E = \{f_1, \ldots, ...
- 121
1
vote
1
answer
103
views
Weighted counting of circular codes
Given a circular code $X$ (for example: $X=\{ w,b \}$) with generating function $u(z)=\sum\limits_{k=0}^{\infty}{u_k z^k}$ (in this example : $u(z)=2z$), the generating function $p(z)=\sum\limits_{k=0}...
- 24.4k
4
votes
2
answers
132
views
Sturmian subword whose reverse is not a subword
Let ${\cal L}_n$ be the set of all subwords of length $n$ of a biinfinite Sturmian sequence, induced by a rotation coding with irrational angle $\theta$.
Take a word $w \in {\cal L}_{2^n}$ and write ...
- 2,223
1
vote
1
answer
195
views
Building the string on $\{0,1\}$ alphabet with $\Omega(n^{2})$ different substrings [closed]
As we know the number of different substrings has the upper bound $O(n^{2})$.
Consider the strings on $\{0,1\}$ alphabet. Can I build a string with $\Omega(n^{2})$ different substrings?
Actually I ...
- 137