Skip to main content

Questions tagged [combinatorics-on-words]

A branch of combinatorics that focuses on the study of words and formal languages

Filter by
Sorted by
Tagged with
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 $\...
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, ...
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 ...
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$,...
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 ...
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 ...
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....
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 ...
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 ...
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 ...
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 ...
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\...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 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-...
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 \...
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 ...
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 ...
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).$...
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$ ...
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_{\...
-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 ...
5 votes
2 answers
245 views

Ordering on words

What are the known computation-friendly well-orderings on words from $A^*$, where $A$ is a finite alphabet, except the standard weightlex and syllable-order?
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 ...
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 ...
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}\ ...
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$. ...
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 ...
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 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 $\{...
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)$):...
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'...
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......
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 ...
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)$...
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 ...
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 ...
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'...
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\}$...
5 votes
2 answers
387 views

Concatenation of strings [closed]

We have two strings (i. e., finite tuples) $A$ and $B$. We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...
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"), ...
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)$. ...
3 votes
1 answer
274 views

Counting triple-free sequences

The Thue-Morse sequence is a triple-free element $(a_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$. The beginning of the ...
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{...
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, ...