All Questions
Tagged with combinatorics-on-words symbolic-dynamics
11 questions
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 ...
- 6,652
4
votes
1
answer
260
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\...
- 6,652
12
votes
1
answer
544
views
Is the set of cube-free binary sequences perfect?
This question is inspired by this one. In that thread, it's established that there are uncountably many cube-free infinite binary strings (where $x \in 2^{\omega}$ is cube-free iff $\forall \sigma \...
- 1,329
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
6
votes
2
answers
319
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......
- 23.7k
7
votes
1
answer
245
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 ...
CommunityBot
- 1
2
votes
1
answer
238
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{...
- 116
4
votes
1
answer
157
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, ...
- 38.7k
3
votes
0
answers
209
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,560
1
vote
1
answer
171
views
Terminology for set of infinite strings with a certain prefix
Let $\mathcal{A}$ be a finite alphabet, and let $C$ be the Cantor space $\mathcal{A}^\omega$ under the product topology.
Given a finite string $s \in \mathcal{A}^*$, let $C(s)$ be the set of all ...
- 2,135
8
votes
1
answer
319
views
Über theorem on unavoidable patterns?
Let $A$ be an alphabet of $k$ symbols,
and $p$ a pattern.
An example of a pattern is $p=XX$, where $X$ is any finite
string of symbols from $A^+$.
Avoiding $p$ is avoiding any subword repeated twice ...
- 24.8k