Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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$ ...
მამუკა ჯიბლაძე's user avatar
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 ...
Alessandro Della Corte's user avatar
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 ...
Gerry Myerson's user avatar
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-...
JRN's user avatar
  • 1,329
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 ...
Igor Pak's user avatar
  • 17.1k
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 ...
მამუკა ჯიბლაძე's user avatar
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 ...
user avatar
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 $\{...
Ville Salo's user avatar
  • 6,652
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 ...
Alessandro Della Corte's user avatar
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}\ ...
Alessandro Della Corte's user avatar