Questions tagged [symbolic-dynamics]

Symbolic dynamics is the study of dynamical systems defined in terms of shift transformations on spaces of sequences. Examples of topics in this area include shifts of finite type, sofic shifts, Toeplitz shifts, Markov partitions and symbolic coding of dynamical systems.

Filter by
Sorted by
Tagged with
9 votes
2 answers
896 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 (...
grok's user avatar
  • 2,489
5 votes
1 answer
284 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\...
Nikita Sidorov's user avatar
1 vote
1 answer
394 views

joining or coupling

given two shift invariant measures in the Bernoulli space $\{0,1\}^{\mathbb{N}}$, is there a way to construct joinings of them? It's very diffcult, in general, to find exactly the minimal joining i.e, ...
Bruno Brogni Uggioni's user avatar
22 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
18 votes
2 answers
1k views

Nice sign-expansions of special surreal numbers

What is the "right" surreal generalization of the fact that a real number $r$ is rational if and only if its sign-expansion is eventually periodic? I can think of more than one natural way to ...
James Propp's user avatar
  • 19.4k
8 votes
1 answer
623 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 ...
Rafael Alcaraz Barrera's user avatar
8 votes
1 answer
411 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 ...
Sebastien Palcoux's user avatar
8 votes
0 answers
258 views

Shift on trivalent directed tree, operator and von Neumann algebra

Let $\mathcal{T}$ be the trivalent directed tree, with two parents and one child for each vertex (see below). Let $\mathcal{V}$ be the set of vertices of $\mathcal{T}$ and $H$ be the Hilbert space $\...
Sebastien Palcoux's user avatar
4 votes
2 answers
253 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\...
Keen-ameteur's user avatar
3 votes
2 answers
355 views

Periodic configurations for elementary cellular automata

Let $L$ be an elementary cellular automaton. Then $L$ acts on $\{0,1\}^{\mathbb{Z}}$. We say that a configuration $w\in\{0,1\}^{\mathbb{Z}}$ is periodic if $L^{(n)}(w)=w$ for some $n\in\mathbb{N}$. ...
Ievgen Bondarenko's user avatar
3 votes
2 answers
404 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 $...
Claude's user avatar
  • 101
3 votes
1 answer
116 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 ...
Veridian Dynamics's user avatar
2 votes
3 answers
634 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