Questions tagged [combinatorics-on-words]
A branch of combinatorics that focuses on the study of words and formal languages
13 questions
13
votes
1
answer
543
views
Number of trivializations of a trivial word in the free group
Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...
- 18.4k
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 ...
- 4,459
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 ...
- 39.9k
21
votes
0
answers
672
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
20
votes
4
answers
3k
views
Cube-free infinite binary words
A word $y$ is a subword of $w$ if there exist words $x$ and $z$ (possibly empty) such that $w=xyz$. Thus, $01$ is a subword of $0110$, but $00$ is not a subword of $0110$. I'm interested in right-...
- 1,329
17
votes
3
answers
736
views
Probability that a word in the free group becomes (much) shorter?
Let $w$ be a word of length $2\ell$ chosen at random on the alphabet $\{x_1,x_1^{-1},x_2,x_2^{-1},\dotsc,x_k,x_k^{-1}\}$. By the reduction $\rho(w)$ I mean what you obtain by deleting substrings of ...
- 20.2k
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 ...
- 18.4k
15
votes
0
answers
487
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 ...
- 17.1k
10
votes
2
answers
1k
views
Ubiquitous Zimin words
Let $w$ be a word in letters $x_1,...,x_n$. A value of $w$ is any word of the form $w(u_1,...,u_n)$ where $u_1,...,u_n$ are words. For example, $abaaba$ is a value of $x^2$. A word $u$ is called ...
user6976
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 $\{...
- 6,652
3
votes
0
answers
387
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
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 ...
- 4,459
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}\ ...
- 4,459