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
13
votes
2
answers
776
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-empty ...
- 261
3
votes
0
answers
195
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.
...
- 717
1
vote
0
answers
111
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 $. ...
- 115
5
votes
0
answers
142
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,597
8
votes
1
answer
319
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 ...
- 24.8k
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 ...
CommunityBot
- 1
1
vote
1
answer
269
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}.$
...
- 24.2k
3
votes
1
answer
116
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, \...
- 446
5
votes
0
answers
336
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 $(\...
- 24.2k
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,393
3
votes
1
answer
466
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 ...
- 18.6k
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
vote
1
answer
132
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$ ...
- 561
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 ...
CommunityBot
- 1
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 ...
- 8,903
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 ...
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- ...
- 23.2k
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 ...
- 2,758
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,769
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 ...
- 170
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(...
- 8,903
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},...
- 2,758
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 ...
- 38.6k
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 ...
CommunityBot
- 1
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$ ...
- 717
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 ...
CommunityBot
- 1
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
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 ...
- 8,903
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 ...
- 23.2k
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(\...
- 3,343
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)^{\...
CommunityBot
- 1
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 $...
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 ...
- 28.2k
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....
- 21
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 ...
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 6,206