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.

learn more… | top users | synonyms

6
votes
0answers
214 views

Topological entropy and periodic sequences of a subshift

Let $\Sigma$ be a two-sided subshift on a finite alphabet $A$. Let $\Sigma_n$ denote all words $x_{-n}\dots x_n\in A^{2n+1}$ such that $(x_k)_{-\infty}^\infty \in \Sigma$ for some $x_k, |k|>n$. ...
3
votes
0answers
173 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$...
3
votes
2answers
139 views

Convex combinations of Bernoulli Measures

How big is the weak-* closure of the set of all (finite) convex combinations of Bernoulli measures among all invariant probability measures? I mean, we are in the symbolic space $\{1,2,\ldots,d\}^{\...
1
vote
0answers
98 views

weak-* versus entropy growth

General question. Let $\eta_{n}$ be a sequence of invariant measures on $\{0,1,2,...,p-1\}^{\mathbb{N}}$ and $B$ the Bernoulli uniform measure. Knowing that $\eta_{n} \rightarrow B$ in the weak-* ...
0
votes
0answers
45 views

The orbit-structure of an automorphism of the full shift

My question concerns reversible cellular automaton rules on a one-dimensional wraparound universe consisting of $m$ sites each capable of being in any of $n$ states, or equivalently, the actions of ...
0
votes
0answers
80 views

A question from One Dimensional Dynamics book by De-Melo and van-Strien

In One Dimensional Dynamics, on page 27 I don't understand how does $(1.7)$ follow; anyone care to explain this to me? Thanks in advance. I am adding some information from the text below: We are ...
0
votes
0answers
162 views

On a certain set of probability measures on a shift

Denote by $\mathbb{Z}_2=\{0,1\}$ the integers modulo 2. Let $S:\mathbb{Z}_{2}^{\mathbb{N}}\times\mathbb{Z}_{2}^{\mathbb{N}} \rightarrow \mathbb{Z}_{2}^{\mathbb{N}}$ be the sum $S(a,b) = a+b$, where $...
0
votes
1answer
116 views

entropy growth of invariant measures - General question

In general, given a sequence of shift-invariant measures $\eta_{n}$ on $\{0,1\}^{\mathbb{N}}$ what to do to guarantee this convergence of entropies: $$h(\eta_{n}) \rightarrow \log2?$$ Because I'm ...
1
vote
1answer
119 views

entropy and d-bar: how do we estimate continuity?

Let $G = \{0,1\}^{\mathbb{N}} = \mathbb{Z}_{2}^{\mathbb{N}}$ be the Bernoulli space of two symbols, let $\sigma$ be the shift map and $M(G)$ the set of $\sigma$-invariant probabilities. Let $\bar{d}$ ...
4
votes
2answers
269 views

Entropy equals zero?

Imagine you have a shift invariant ($\sigma$-invariant) probability measure $\eta$ in the Bernoulli space $\{0,1\}^{\mathbb{N}}$. Define $\mathcal{P} = \{[0],[1]\}$; $\mathcal{P}^{n} = \mathcal{P}\...
2
votes
1answer
126 views

Multi dimensional symbolic dynamics

I want to learn Multi dimensional symbolic dynamics. can you point to any recent thesis containing a good exposition or lecture notes?
0
votes
1answer
148 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, ...
5
votes
1answer
139 views

When is the time one map of a suspension flow ergodic?

I'm sure the answer to the following question is well known but I couldn't find the answer I needed. Let $(\Sigma,\sigma)$ denote the full shift on $k$ symbols and let $\mu$ be an invariant measure ...
16
votes
2answers
577 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 ...
1
vote
1answer
77 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 ...
3
votes
2answers
173 views

Does the 2-shift map have a root automorphism?

By the 2-shift map I mean the map $T:\{0,1\}^\mathbb{Z}\to \{0,1\}^\mathbb{Z}$ that shifts the sequence leftwise. By a root I mean an homeomorphism $\psi:\{0,1\}^\mathbb{Z}\to\{0,1\}^\mathbb{Z}$ that ...
2
votes
1answer
198 views

Embeddings of subshifts

Consider $(X,\sigma_X)$ and $(Y, \sigma_{Y})$ be subshifts of the one sided shift in two symbols. Assume that $(X,\sigma_X)$ is a transitive subshift of finite type and $(Y, \sigma_{Y})$ is a ...
1
vote
0answers
88 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}$. ...
11
votes
2answers
524 views

On the boundary of the twindragon

Let $\mathcal T$ be the famous twindragon, i.e., $$ \mathcal T=\left\{\sum_{n=0}^\infty a_n\left(\frac{1+i}2\right)^n : a_n\in\{0,1\}\right\}. $$ Then, as is well known, $\mathcal T$ has a non-...
9
votes
1answer
430 views

Perron-Frobenius theory for reducible matrices

Can someone suggest some sources/references dealing with the Perron-Frobenius theory for nonnegative matrices that are reducible? Specifically, if $A\ge 0$ is a $d\times d$ matrix with no assumptions ...
3
votes
0answers
116 views

Topological pressure for subshifts on a countable alphabet

Apologies for asking two similar questions within a week of each other, I had hoped that asking a finite alphabet version of this question would lead to enlightenment but unfortunately it didn't. ...
4
votes
3answers
211 views

Approximating Subshifts From Below

I'm looking to understand how to approximate certain countable alphabet subshifts by Markov shifts, and realised that I don't know how to do it even in the finite alphabet case. My guess is that the ...
1
vote
0answers
97 views

The value of the sequence generated by the substitution

Given a substitution $1\to 100$, $0\to 01$, then we have $1\to 100\to1000101\to10001010110001100\to\cdots$, we denote this limits (fixed point of this substitution) as $(a_n)$, given $\beta>1 $. ...
5
votes
0answers
118 views

Growth in families of trees

I'm hoping that the question below is simple thermodynamic formalism, but I can't quite make it work. Any help would be very welcome. Let $\Sigma:=\{0,1\}^{\mathbb N}$ and let $\Sigma^*$ be the set ...
3
votes
1answer
162 views

Substitutions and Sturmian sequences

We know that any substitution can generate sequence, for example the Fibonacci substitution: $\sigma(0)=01, \sigma(1)=0$, then we can define a Sturmian sequence $\omega$, i.e., the fixed point of $\...
5
votes
1answer
106 views

Ferenczi: minimal, uniquely ergodic, sublinear complexity systems are not strongly mixing

The following result is on page 26 of this paper by Ferenczi [PDF]. Corollary 3. A minimal and uniquely ergodic system of sub-affine complexity cannot be strongly mixing (i.e., $\mu(T^nA \cap B) \...
2
votes
2answers
324 views

Brun's algorithm

Does anyone have an exact reference for the weak convergence (convergence in angle) of Brun's subtractive multi-dimensional continued fractions algorithm (in all dimensions)? I have been given ...
8
votes
1answer
255 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 ...
1
vote
1answer
225 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}.$ ...
3
votes
1answer
77 views

For a summable function, with summable variation, prove that $\sup_{i \in I} \sup_{x \in [i]}|f(x)| \exp((t-1) sup_{x \in [i]}f(x) )$ is bounded

Let $X = \mathbb{N}^\mathbb{N}$ and $f: X \to \mathbb{R}$ be a function such that $$|f|_{var}= \sum_{n=1}^{\infty} var_n f < \infty,$$ where $var_n f = sup\{|f(x)-f(y)|: x,y \in X , x_k = y_k, \...
1
vote
1answer
178 views

Cycles in directed graphs

Let G be a finite directed graph (allowing multiple edges). We define a cycle (as usual) to be a sequence of edges $e_0, e_1, \dots, e_{n-1}$ (up to cyclic permutation) such that the terminal vertex ...
1
vote
1answer
116 views

Group action of $G<\mathbb Z^\infty_2$ over the Golden mean shif [closed]

I'm am looking for an action of an infinite subgroup of $\mathbb Z^\infty_2$ over the golden mean shift space $$X=\{x\in \{0,1\}^\mathbb N : x_i=1\Rightarrow x_{i+1}=0\}$$ such that any element of $G$ ...
0
votes
1answer
194 views

Is any invariant, ergodic measure with full support on an irreducible Markov shift a Markov measure?

I have this question I have been struggling with for a while. It seems rather intuitive, however, I was not able to proof it yet: Let $\Omega = \{1,2,\cdots,N\}$ a finite alphabet, $\Sigma \subset \...
5
votes
0answers
266 views

Deterministic shifts

We consider (topological) dynamical systems $(\Omega, S)$, where $S$ is the shift $(Sx)_n=x_{n+1}$, and $\Omega\subset[0,1]^{\mathbb Z}$ is a compact, shift invariant subspace. I call such a system $(\...
4
votes
1answer
167 views

Graph presentation of Lexicographic shifts

Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic ...
2
votes
1answer
91 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- ...
1
vote
1answer
166 views

Find a sequence with uniform frequencies and recurrent property

Given any 4 positive numbers $p_{00}\,,p_{01}=p_{10}\,,p_{11}$,such that the sum of the 4 numbers is 1, now I want to find a sequence in $\{0\,,1\}^\mathbb{N}$ such that this sequence has uniform ...
0
votes
2answers
189 views

The Book for ergodic theory on SFT in dimension $D>1.$

I have been unable to find a good reference for a book that study in details ergodic theory on sub shifts of finite type in dimension $D>1.$ The only reference that I got was actually a book by ...
6
votes
1answer
228 views

Renewal systems: Intrinsic ergodicity and a question related to the Adler's conjecture

Consider the alphabet $\mathcal{A} = \{0,1\}$ and consider a finite set of words $W = \{\omega_1, \ldots , \omega_n\}$ over $\mathcal{A}$. Then the renewal system $\Sigma_{W}$ generated by $W$ is ...
6
votes
3answers
497 views

A weak-mixing, zero entropy measure on the 2-shift which gives equal weight to both symbols

I am currently sketching a paper in the general area of symbolic dynamics in which I would like to be able to use the following fact: Proposition (proposed): there exists a shift-invariant ...
2
votes
1answer
128 views

Does conjugacy preserve the set of synchronizing blocks?

A synchronized system is a transitive shift space $X$ which has a synchronizing block $v$, that is $v$ is an admissible block for $X$ and whenever $vw$ and $uv$ are admissible blocks in $X$, then $uvw$...
2
votes
2answers
172 views

Mixing coded systems and period of their graph presentations

A coded system [see F. Blanchard, G. Hansel, Systèmes codés, Theoretical Computer Science, Vol. 44, 1986, pp. 17-49, http://dx.doi.org/10.1016/0304-3975(86)90108-8. (http://www.sciencedirect.com/...
3
votes
1answer
158 views

Automorphisms of strictly ergodic shift spaces

Let $X$ be a strictly ergodic shift space, and $\omega_1$, $\omega_2$ be two different points in $X$. Is there an automorphism $\Psi$ of $X$ such that $\Psi(\omega_1)=\omega_2$? By an automorphism I ...
4
votes
1answer
211 views

Is there a one-dimensional subshift of positive entropy s, all of whose sub-subshifts also have entropy s?

A subshift is a subset $X$ of $A^\mathbb{N}$ or $A^\mathbb{Z}$ (with $A$ finite), such that $X$ is topologically closed and closed under the shift operation. The shift operation is defined by $\sigma(...
4
votes
1answer
662 views

Intuition of Kolmogorov-Sinai entropy

For a measurable entropy of measurable transformation $T$ from $(X,\mathcal{B},m)$ to itself. For each finite measurable partition $\mathcal{A}=\{A_i\}_{i=1}^{m}$ of $X$, we can define $h(\mathcal{A},...
1
vote
2answers
152 views

Estimation of number of ways to concatenate strings of the form $01^k2^k$ to create a string of length n

In symbolic dynamics, the context-free shift is the set of biinfinite concatenations of strings of the form $01^k2^k$ for $k\in\mathbb{N}\cup\lbrace 0\rbrace$. I've reduced a certain problem to ...
28
votes
5answers
2k views

What is the effect of adding 1/2 to a continued fraction?

Is there a simple answer to the question "what happens to the continued fraction expansion of an irrational number when you add 1/2?" A closely related question is "what happens to such an expansion ...
2
votes
2answers
259 views

probability measures with entropy equal to nonnegative number

Is it true that for a given nonnegative number, there exists a measure-theoretical entropy value (supremum of entropies of all partitions under a measure-preserving transformation) that equals this ...
6
votes
1answer
302 views

Relative irreducibility

Let $X$ be a one-dimensional one-step irreducible shift of finite type and let $\pi$ be a one-block factor code from $X$ to a sofic $Y$. Suppose $y$ is a right transitive point of $Y$ and $\pi(u)=y$ ...
6
votes
1answer
497 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 ...