Questions tagged [combinatorics-on-words]
A branch of combinatorics that focuses on the study of words and formal languages
24
questions with no upvoted or accepted answers
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,263
21
votes
0
answers
667
views
Avoidable words
Let $u(x_1,...,x_n)$ be a word, $k\in \mathbb{N}$. We say that $u$ is $k$-avoidable if there exists an infinite word in $k$ letters $\{a_1,...,a_k\}$ which does not contain values of $u$ (i.e. words ...
user6976
17
votes
0
answers
530
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
15
votes
0
answers
481
views
Word complexity of primes mod 4
For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
- 16.3k
13
votes
0
answers
289
views
Computing exact or asymptotics for number of strings over an alphabet of size $n$ that have no non-trivial substrings that appear more than once
I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length $...
- 261
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 ...
- 19.4k
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$.
...
- 40.9k
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 ...
- 151
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
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 ...
- 1,064
4
votes
0
answers
121
views
Covariance matrix for number of powers in a word
A word over the alphabet $\{0,1\}$ of length $n$ may contain squares, cubes, and generally $k$th powers, where $2\le k\le n$. Let $O_k(w)$ denote the number of $k$th power occurrences in the word $w$.
...
- 24.6k
3
votes
0
answers
82
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
3
votes
0
answers
207
views
Repartition of 1's in the "Chacon word"
Consider the "Chacon words": $B_0=0$ and $B_{n+1} = B_nB_n1B_n$. The word $B_n$ has $\ell_n := \frac{3^{n+1}-1}{2}$ digits and the number of $1$'s in $B_n$ is $\ell_n - 3^n = \ell_{n-1} \sim \ell_n/3$...
- 2,433
3
votes
0
answers
184
views
Generalised de Bruijn Graph
I have encountered sets of the following type, consisting of words over a finite aphabet $A$.
If $S$ is such a set, then
$S$ is finite,
No word in $S$ is part of another element of $S$, and
every ...
user22882
3
votes
0
answers
386
views
Software for Combinatorial Algebra sought
I am looking for software which helps me do straightforward tasks in combinatorial algebra. Let me give an example of what I mean by a straightforward task:
I have two graded (generally ...
2
votes
0
answers
93
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 ...
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. ...
- 6,337
2
votes
0
answers
114
views
Zero-one links: how many, and how to produce?
For $m \geq 1$, define a link to be a zero-one word $w=d_0d_1 \ldots d_k$, where $d_0=0$ and $k=2^m-1$ , such that the words
$$ w_0=0^{m-1}d_0, w_1=w_0d_1, w_2=w_1d_2, \ldots, w_k = w_{k-1}d_k $$
...
- 3,443
2
votes
0
answers
183
views
Words with Local plus Global Constraints
While doing estimates on the complexity of an algorithm I have run into a word-combinatorial problem with both a local and a global constraint.
This seems to be a rather general situation and I'm ...
- 121
2
votes
0
answers
213
views
Counting strings with alternating letters with generating functions
It is a classical problem that of finding the generating function (GF) of the number of strings with length $n$ having $m$ different letters (basically, the problem reduces to that of writing the ...
- 121
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$,...
- 959
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,263
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 ...
- 602
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, ...
- 121