All Questions
Tagged with symbolic-dynamics co.combinatorics
21 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 ...
- 39.9k
19
votes
2
answers
581
views
Sequences with 3 letters
For a positive integer $n$ I would like to construct long sequences consisting of 0, 1 and 2's such that for any two subsequences consisting of $n$ consecutive elements the number of 0's , 1's or 2'...
- 2,286
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 \...
- 3,992
10
votes
3
answers
2k
views
How to characterize a Self-avoiding path.
I cannot find any answer to that apparently simple problem :
On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}.
Is there a rule ...
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 ...
- 151k
8
votes
1
answer
436
views
The graph of Rule 110 and vertices degree
Consider the elementary cellular automaton called Rule 110 (famous for being Turing complete):
It induces a map $R: \mathbb{N} \to \mathbb{N}$ such that the binary representation of $R(n)$ is ...
8
votes
1
answer
414
views
Breaking efficiently a binary sequence into given strings
Suppose we are given a finite collection of finite binary strings $\mathcal{S}$, of various lengths. Our task is to express any binary sequence $x\in 2^\mathbb{N}$ as juxtaposition of strings taken ...
- 60.6k
6
votes
2
answers
148
views
Decidability of (restricted) periodicity of Wang tilings
Consider a Wang tiling (given a subset of $C^4$ for a finite set $C$ of colours, e.g.). It's well-known to be undecidable whether there exists a tiling, and also whether there exists a periodic tiling....
- 2,519
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......
- 115
5
votes
0
answers
366
views
A Collatz-like map?
Consider the map $\psi$ acting on triples $(a\leq b\leq c)$ of three positive natural integers with $\mathrm{gcd}(a,b,c)=1$ as follows:
Set $$(a',b',c')=\left(\frac{a}{\mathrm{gcd}(a,bc)},\frac{b}{\...
- 17.9k
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\...
- 23.2k
3
votes
1
answer
91
views
Asymptotic growth rate for primitve S-adic systems
It is known that for a primitive substitution $S:\mathcal{A}\to \mathcal{A}^+$, there exists constants $c,C>0$ such that
$$ c\theta_S^n \leq \vert S^n(a)\vert \leq C \theta_S^n \quad \text{for all} ...
- 633
3
votes
1
answer
193
views
'Trivial' lower bounds for pattern complexity of aperiodic subshifts
I recently asked in this thread about lower bounds on the complexity in the case where we have an aperiodic subshift. If I denote $c_n(\Omega)$ as the number of possible patterns on $Q_n= \big\{ 0,...,...
- 633
2
votes
1
answer
105
views
Constructing an interval exchange given a prescribed trajectory
Given a prescribed trajectory, is it possible to construct an interval exchange having this trajectory?
For example, given a 3-letter word (like aaabbbccabcaaa ), is it possible to construct a 3- ...
- 73
2
votes
1
answer
183
views
A sensitive 2-dimensional cellular automaton with a blocking word
I'am a Ph.D student in the domain of discrete dynamical systems. My thesis is about spectral properties of cellular automata in higher dimension.
Kurka gives a classification for one dimensional ...
2
votes
1
answer
143
views
Search for a general formula from known iterative relation
$F$ is a mapping among $\{\theta_{n_1n_2}\}$, with $\eta_{1/2}$ being arbitrary constants involved.
$F: \theta_{n_1n_2} \rightarrow \theta_{n_1+1n_2}+\theta_{n_1n_2+1}+\eta_{1}n_1\theta_{n_{1}-1n_{2}} ...
- 23
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
0
answers
92
views
Conjugacy between piecewise linear circle maps
Let $\mathcal{M}$ the Mandelbrot set,
$\mathcal{M}=\{c \in \mathbb{C}: \{Q_c^n(0) \}_{n \in \mathbb{N}} \text{ is bounded, where } Q_c(z)=z^2+c \}$
And let the hyperbolic or stable component, $H_n=\{ ...
- 271
1
vote
1
answer
269
views
A problem in symbolic dynamics
I got a fun problem.
Define the alphabet $\mathcal{A}=\{0,1,2\}$ and the set $\mathcal{A}^{\leq n}=\{ x_1x_2\ldots x_n: x_i\in \mathcal{A}\}$ of words of length $n,$ for each $n\in\mathbb{N}.$
...
- 1,805
1
vote
2
answers
329
views
Sufficient conditions for periodic tiling by Wang tiles
I'm recently interested in whether a sub-shift of finite type contains a doubly-periodic problem, when the set of configurations is of the sort $\mathcal{A}^{\mathbb{Z}^2}$. When $Q_2=\{0,1\}^2$, and ...
- 633
1
vote
1
answer
202
views
Overlaying two domino-like constructions such that all individual pairs of domino-like cells in the overlay have matching symbols
Imagine I have two $n$ x $m$ assemblies of $P = (n*m)$ unit square cells on the plane, $(c_{(a,1)}, ..., c_{(a,P)}) \in A$ and $(c_{(b,1)}, ..., c_{(b,P)}) \in B$, where every cell, $c_k$, in a ...
- 13