# Questions tagged [combinatorics-on-words]

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

102 questions
Filter by
Sorted by
Tagged with
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 ...
• 163
1 vote
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$,...
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 ...
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 ...
• 419
163 views

• 129
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
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 ...
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 ...
118 views

• 18.2k
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$. ...
• 41k
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 ...
• 1,064
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. ...
• 6,437
187 views

• 435
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 ...
• 19.3k
316 views

• 5,410
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, ...
• 2,085
1 vote
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 ...
410 views

• 121
1 vote
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}...
• 26.2k