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.
189 questions
4
votes
1
answer
224
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
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
1
vote
1
answer
176
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 ...
- 41
0
votes
2
answers
305
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 ...
- 1,805
7
votes
1
answer
292
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 ...
7
votes
3
answers
792
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 ...
- 6,206
2
votes
1
answer
147
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$...
- 1,658
2
votes
2
answers
209
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/...
- 1,658
3
votes
1
answer
206
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 ...
- 1,658
5
votes
1
answer
432
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(...
- 1,601
8
votes
1
answer
2k
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,706
1
vote
2
answers
166
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 ...
- 13
29
votes
5
answers
4k
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 ...
- 3,547
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
2
votes
2
answers
269
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 ...
- 63
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
6
votes
1
answer
327
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$ ...
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 ...
1
vote
0
answers
190
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 ...
- 325
0
votes
1
answer
445
views
Recurrence theorems [closed]
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 ...
- 9
2
votes
1
answer
344
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 ...
6
votes
1
answer
383
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
1
answer
317
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 $T(\...
- 2,619
2
votes
1
answer
421
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 $exp(-nh-...
2
votes
0
answers
304
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
0
answers
105
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 $\mu=(p,1-p)^{\...
- 325
3
votes
2
answers
370
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 $...
- 303
5
votes
3
answers
773
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 ...
- 701
6
votes
4
answers
943
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 B....
user6976
4
votes
2
answers
594
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 ...
- 13k
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
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
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
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
1k
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 ...
- 18.7k
4
votes
1
answer
273
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$ ...
- 15.4k
6
votes
5
answers
2k
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 with ...
- 15.4k
8
votes
1
answer
605
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 ...
- 15.4k
4
votes
2
answers
1k
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 ...
- 15.4k