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
10 votes
1 answer
441 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 ...
thematdev's user avatar
  • 163
1 vote
0 answers
167 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$,...
lyrically wicked's user avatar
2 votes
0 answers
96 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 ...
José Victor Gomes's user avatar
6 votes
1 answer
264 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 ...
Or Meir's user avatar
  • 419
2 votes
1 answer
163 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....
lyrically wicked's user avatar
3 votes
0 answers
84 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 ...
Bogdan's user avatar
  • 183
4 votes
1 answer
251 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\...
Anthony Quas's user avatar
  • 22.5k
1 vote
1 answer
117 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 ...
lyrically wicked's user avatar
7 votes
2 answers
309 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$ ...
lyrically wicked's user avatar
3 votes
1 answer
258 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 ...
Alessandro Della Corte's user avatar
5 votes
1 answer
119 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 ...
rtsss's user avatar
  • 477
5 votes
1 answer
290 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).$...
Clark Kimberling's user avatar
5 votes
0 answers
112 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 ...
user158448's user avatar
2 votes
1 answer
342 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$ ...
Dattier's user avatar
  • 3,767
4 votes
1 answer
233 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 ...
Alessandro Della Corte's user avatar
2 votes
1 answer
130 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_{\...
JustAsking's user avatar
-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 ...
JustAsking's user avatar
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 ...
Alessandro Della Corte's user avatar
12 votes
1 answer
416 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 ...
Clark Kimberling's user avatar
2 votes
1 answer
118 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}\ ...
Alessandro Della Corte's user avatar
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 ...
Alessandro Della Corte's user avatar
2 votes
3 answers
634 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 ...
Alessandro Della Corte's user avatar
4 votes
2 answers
254 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-...
Pace Nielsen's user avatar
  • 18.2k
9 votes
0 answers
444 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$. ...
Taras Banakh's user avatar
4 votes
0 answers
143 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 ...
Christoph Mark's user avatar
2 votes
0 answers
187 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. ...
Ville Salo's user avatar
  • 6,437
6 votes
1 answer
187 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 $\{...
Ville Salo's user avatar
  • 6,437
9 votes
2 answers
381 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)$):...
Bjørn Kjos-Hanssen's user avatar
1 vote
1 answer
107 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'...
frafour's user avatar
  • 435
10 votes
0 answers
394 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 ...
H A Helfgott's user avatar
  • 19.3k
6 votes
2 answers
316 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......
Adam Quinn Jaffe's user avatar
4 votes
1 answer
228 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)$...
user avatar
7 votes
1 answer
240 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 ...
Darren Ong's user avatar
8 votes
1 answer
211 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\}$...
Mark Wildon's user avatar
  • 10.8k
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"), ...
Harry Altman's user avatar
  • 2,575
3 votes
1 answer
121 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)$. ...
Domenico Zambella's user avatar
2 votes
1 answer
227 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{...
Mikhail Tikhomirov's user avatar
4 votes
1 answer
154 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, ...
Nikita Sidorov's user avatar
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 ...
Stella Biderman's user avatar
12 votes
1 answer
410 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=\{...
BharatRam's user avatar
  • 939
11 votes
1 answer
326 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 ...
Bjørn Kjos-Hanssen's user avatar
3 votes
0 answers
280 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 ...
BharatRam's user avatar
  • 939
4 votes
1 answer
163 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 ...
DavidHume's user avatar
  • 741
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 ...
Matthew Quartz's user avatar
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 ...
D. Ror.'s user avatar
  • 399
17 votes
0 answers
531 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$...
user avatar
5 votes
1 answer
389 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-...
barry's user avatar
  • 51
3 votes
1 answer
278 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$...
Bjørn Kjos-Hanssen's user avatar
0 votes
0 answers
182 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, ...
user95393's user avatar
  • 121
1 vote
1 answer
105 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}...
Mare's user avatar
  • 26.2k