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

2
votes
1answer
129 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 ...
7
votes
1answer
196 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
187 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
62 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
106 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
101 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
88 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
220 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
129 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
80 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- ...
0
votes
2answers
140 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
189 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
272 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
114 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 ...
2
votes
2answers
141 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. ...
3
votes
1answer
122 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 ...
2
votes
1answer
110 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 ...
1
vote
0answers
47 views

A criterion or algorithm for polynomial which admits Markov partition on its Julia set

For a given polynomials $P(z)$, whether there exists general algorithm to check it admits a Markov partition on its Julia sets. (in finite computation time.) May be it is more difficult for the ...
4
votes
1answer
318 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 ...
1
vote
2answers
125 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 ...
27
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
249 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
280 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
389 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 ...
1
vote
0answers
136 views

Entropy of factors of Bernoulli schemes

Let $X$ be a Bernoulli scheme. A factor $\psi: X \to Y$ is finitary if for almost every $x \in X$ there exist integers $m \leq n$ such that the zero coordinates of $\psi(x)$ and $\psi(x')$ agree for ...
0
votes
1answer
279 views

Recurrence theorems

Bonjour, I need some help regarding recurrence theorems in shift spaces. I am aware of Poincaré's Recurrence Theorem, but I'm sure I've heard of another one telling about the time required to get back ...
2
votes
1answer
221 views

Coded Systems and dense subsets

A shift space $(X, \sigma)$ is a coded system if there exist a countable collection of finite words $(\omega^n)_{n \in \mathbb{N}}$, called generators, such that $X$ is the closure of the set of ...
5
votes
1answer
255 views

Limits of intrinsically ergodic systems

Let $(X_i)$ be a sequence of compact metric spaces and $(f_i)$ a sequence of transitive transformations $f_i:X_i \to X_i$ with $0 < h_{top}(f_i) < \infty$. The sequence of dynamical systems ...
0
votes
1answer
272 views

Modulo dynamics on [0,1)

For $T: \mathbb{R} \mapsto \mathbb{{R}_{+}}$, we have $\{ {T}^{n}(\theta)\ mod \ 1\} \subset [0,1)$. (where ${T}^{n}(\theta)$ means applying $T$ $n$ times on $\theta$, not the $n$th power of ...
2
votes
1answer
268 views

Measure of large cylinder sets

Given an ergodic measure m on a shift space, by Shannon-Mcmillan-Breiman Theorem, up to at most an $\epsilon$-portion, all cylinder sets of length $n$ (large enough) have $m$-measure between ...
2
votes
0answers
186 views

Does an aperiodic dynamical system have $n$-markers for any $n$?

I was wondering if a certain lemma in an article by Downarowicz holds in a more general setting (see details below): Let $(X,T)$ be a topological dynamical system. I.e. $X$ is a compact Hausdorff ...
1
vote
0answers
95 views

Finitary factors of Bernoulli schemes that pair duals

This question is related to my question: entropy preserving finitary factor maps of Bernoulli schemes. Hopefully, this one is a bit easier. Let $X=\{0,1\}^\mathbb{Z}$ with measure ...
3
votes
2answers
334 views

How to detect frequency?

Let $J$ be an arc in $\mathbb{S}^{1}\subset\mathbb{C}$ (no matter open or closed) and $\alpha\in(0,2\pi)$ be an angle such that $\alpha/\pi$ is irrational. Consider in $\mathbb{S}^{1}$ the sequence ...
3
votes
3answers
529 views

Periodic sequences in symbolic dynamics

I'm an REU student who has just recently been thrown into a dynamical system problem without basically any background in the subject. My project advisor has told me that I should represent regions of ...
6
votes
4answers
550 views

Subshifts with the same entropy

It is known that two Markov subshifts with the same entropy are "almost isomorphic" (up to a subset of measure 0) if the entropy is a logarithm of an integer (see R. L. Adler, L. W. Goodwyn, and ...
3
votes
2answers
412 views

Other realms for studying symbolic dynamics

I hope to find an online version of accessible texts in symbolic dynamics. Marcus and Lind have a text I hope to get online. What I don't know is if any text yet exists that considers symbolic ...
13
votes
1answer
423 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 ...
7
votes
3answers
953 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
1answer
357 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 ...
6
votes
2answers
646 views

topologically mixing subshifts without ergodic measures

Are there examples of subshifts (that is, closed shift-invariant subsets of the full shift {$1...n$}${}^{\mathbb{Z}}$) on which the shift is topologically mixing, which admit a shift-invariant ...
3
votes
0answers
180 views

What is known about first return times to Markov partitions for Anosov diffeomorphisms?

Consider an Anosov diffeomorphism $T: M \rightarrow M$ and a corresponding Markov partition $\mathcal{R}$ of $M$. For $x \in M$, let $\mathcal{R}(x)$ denote the element of $\mathcal{R}$ containing $x$ ...
5
votes
5answers
1k views

How can generic closed geodesics on surfaces of negative curvature be constructed?

As far as I understand it the closing lemma implies that closed geodesics on surfaces of negative curvature are dense. So: how can they be constructed in general? A concrete answer that dovetails ...
6
votes
1answer
460 views

A regularity property of transition matrices for the cat map

I've noticed a rather strange phenomenon (not important for my particular research, but interesting) and wouldn't be surprised if someone more versed in symbolic dynamics (i.e., just about anyone who ...
4
votes
2answers
996 views

Proper families for Anosov flows

So I've been skimming Bowen's 1972 paper "Symbolic Dynamics for Hyperbolic Flows" hoping it would give me some insight into how to build a Markov family for the cat flow (i.e., the Anosov flow ...