All Questions
Tagged with ds.dynamical-systems symbolic-dynamics
9 questions
10
votes
2
answers
1k
views
Decidability of periodic tilings of the plane
I'm interested in tilings of the plane by squares, with labels on the edges. It's well known that (1) the question "can one tile the plane with the following finite set of tiles?" is undecidable, and (...
- 2,519
5
votes
1
answer
289
views
The spectral radius of a binary matrix - polynomial growth?
(This is a follow-up to The spectral radius of a binary matrix)
Let $\mathcal B_n$ denote the set of $n\times n$ matrices with entries in $\{0,1\}$.
QUESTION. Is there a $\delta\in\bigl(0,\frac12\...
- 2,135
9
votes
1
answer
210
views
Can the full shift be embedded in a flow?
Write $I=[0,1]$, and let $S$ be the shift on $X=\{ (x_n)_{n\in\mathbb Z} : x_n\in I^k \}$. Is there a flow $\phi_t$ on $X$ with $\phi_1=S$? Here I require that $\phi_t$, for fixed $t$, is at least a ...
- 24.2k
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
631
views
Aproximating dynamical systems by intrinsically ergodic systems
Let $X$ be a compact metric space and $f:X \to X$ a continuous map. We say that $(X,f)$ is approximated from below by a sequence of compact metric spaces $(X_i)_{i \geq 1}$ and a sequence of ...
4
votes
2
answers
273
views
Lower bounds for pattern complexity of aperiodic subshifts
In the setting of symbolic dynamics over $\mathbb{Z}^d$, one can define for the $n$-th pattern complexity of a given a subshift $\Omega\subseteq \mathcal{A}^{\mathbb{Z}^d}$ as
$$ c_n(\Omega):= \Big\...
- 633
3
votes
2
answers
416
views
Fast algorithms for external angle computations
Two related problems related to the complex quadratic polynomial $f_c(z) = z^2 + c$ and Mandelbrot and/or Julia sets:
find an external angle $\theta_c$ for a complex point $c$
find a complex point $...
- 111
3
votes
1
answer
120
views
Almost one-to-one endomorphism of minimal subshift?
Let $(X,T)$ be a minimal subshift. Can it happen that an endomorphism $\varphi\colon (X,T) \to (X,T)$ is almost 1-to-1 but not 1-to-1? Can it happen that a factor $\pi\colon (X,T) \to (Y,T)$ between ...
2
votes
3
answers
638
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