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
3
votes
2
answers
368
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}$.
...
- 6,652
3
votes
1
answer
392
views
Is it known that MLC is sufficient to prove the density of hyperbolic conjecture of rational maps (or not)
Is it known that local connectivity of the Mandelbrot set (MLC) is sufficient prove the density of hyperbolic conjecture of qudratic family.
I wondered is it known that the MLC is not enough (or ...
- 106
4
votes
1
answer
176
views
Measures maximizing entropy in a set of measures with fixed average for some observable
Let $\Omega$ be the set of all infinite binary sequences $(x_i)_{i\ge 0}$ endowed with the product topology coming from discrete topology on $\{0,1\}$.
Consider $0<\alpha<1$ and let $$K_\alpha=\{...
- 8,903
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 ...
- 63.9k
42
votes
2
answers
3k
views
Can one "hear" the shape of a polygon via external reflections?
This question is a rough analog of Kac's "Can One Hear the Shape of a Drum?"
A closer analog is the recent "Bounce Theorem" that says, roughly, the shape of a polygon is determined by its billiard-...
- 237k
2
votes
1
answer
191
views
Synchronised $\beta$-shifts
I have been reading some papers recently, in particular, Blanchard's paper $\beta$-expansions and symbolic dynamics which state that a $\beta$-shift $S_{\beta}$ is a synchronised shift if and only if ...
- 1,658
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-...
- 1,228
8
votes
0
answers
269
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 $\...
3
votes
1
answer
125
views
Topological universality for Cantor maps
I am afraid this question might be very naïve, but I find it hard to locate a reference that does not answer a slightly different question.
Consider the Cantor set $C$ and a continous map $f: C\to C$ ...
- 63.9k
5
votes
1
answer
289
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\...
- 23.2k
3
votes
2
answers
427
views
Subshifts of finite type of guaranteed positive entropy
Let $\Sigma$ be a subshift of finite type (SFT) with the alphabet $\{0,1\}$, which is given by the set of forbidden words $\mathcal F$, all of length $N$.
Question. Is there a $\delta>0$ such ...
- 2,621
2
votes
1
answer
238
views
Unique(ish) infinite string avoiding a set of patterns
Let $\Sigma$ be a finite alphabet of size at least 2. A (possibly infinite) string $s$ over alphabet $\Sigma$ encounters a pattern $p \in \mathbb{N}^*$ iff there is a non-erasing morphism $f: \mathbb{...
- 116
4
votes
1
answer
157
views
Subshifts with a free semigroup
Let $X$ be a subshift on a finite alphabet. I'm interested in the following property: there exist words $s,t\in\mathcal L(X)$ (the language of $X$) such that $\{s,t\}^*\subset \mathcal L(X)$. That is, ...
- 38.6k
15
votes
2
answers
648
views
Is the following series consisting of equally distributed $\pm 1$ bounded?
Apologise in advance if this problem isn't research-level (I'm quite certain it isn't). It's just I found it quite intriguing because it turned out to be much more subtle than it appeared at my first ...
- 18.7k
1
vote
1
answer
120
views
Partitioning a subset of a subshift into comparable parts
Let $(X,\mu,\sigma)$ be a subshift on a finite alphabet, which we assume to be mixing. That is, for any cylinders $C, C'$ we have $\mu(\sigma^{-n}C\cap C')\to\mu(C)\mu(C')$ as $n\to+\infty$. We also ...
- 2,135
4
votes
0
answers
177
views
Explicit symbolic codings
The short version of my question is that I need examples of explicit continuous symbolic codings of invertible dynamical systems.
Here's a longer version. Suppose $(\Omega,\mu,T)$ is an invertible ...
- 2,135
7
votes
3
answers
217
views
Besicowitch distance between sets of invariant measures, ergodic vs non-ergodic
When working with Dominik Kwietniak and Jakub Konieczny, the question appeared:
Let $X$ and $Y$ be two subshifts on the same alphabet, $M(X)$, $M(Y)$ the sets of shift-invariant measures on $X$ and $...
- 330
6
votes
0
answers
343
views
Had this theorem in Tresser's article been proven somewhere?
The article in question is About Some Theorems by L.P. Sil'nikov by Charles Tresser. I am interested in the theorem C from page 453 and a particular application of such theorem which is illustrated ...
- 165
9
votes
1
answer
210
views
Can the full shift be embedded in a flow?
Write $I=[0,1]$, and let $S$ be the shift on $X=\{ (x_n)_{n\in\mathbb Z} : x_n\in I^k \}$. Is there a flow $\phi_t$ on $X$ with $\phi_1=S$? Here I require that $\phi_t$, for fixed $t$, is at least a ...
- 63.9k
1
vote
1
answer
375
views
Inverse map of chaotic map : confusion and request for information
This is based from the paper titled, "Chaos-Based Simultaneous Compression and Encryption for Hadoop" in Section 2.3.1 download link
The Authors say that given a symbolic sequence, it can be encoded ...
- 135
1
vote
1
answer
279
views
Beginners level question : symbolic dynamics and notations
Let $f(.)$ be a chaotic 1 D Map which produces a scalar valued time series where the first iterate is obtained from an initial condition $x[0]$ as $x[1] = f(x[0],\mu)$ where $\mu$ is the control ...
- 1,228
3
votes
2
answers
398
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 ...
- 63.9k
0
votes
1
answer
231
views
A modified Cantor and its measure
Recall that Cantor set can be defined as the set of numbers in $[0,1]$ that don't contain $1$ when written in ternary number system.
Alternatively if we consider the map $\varphi: [0,1]\to [0,1]$, $...
- 23.2k
9
votes
0
answers
602
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$.
...
- 2,135
15
votes
0
answers
3k
views
Weak$^*$ convergence of measures vs. convergence of supports
Let $X$ be a compact metric space and let $\mathcal M(X)$ denote the set of probability measures on $X$. For $\mu\in\mathcal M(X)$ we write $\text{supp} \mu$ for the support of $\mu$. It is easy to ...
- 1,658
6
votes
0
answers
255
views
Completeness of the space of measures under $d$-bar metric
Does anybody know the reference to a proof of the following fact (which is not hard to prove, but seems to be well-known, see here): The space of shift-invariant measures under Ornstein's d-bar metric ...
CommunityBot
- 1
7
votes
1
answer
273
views
What is the simplest SFT on $\mathbb{Z}^2$ that has no periodic points?
An SFT (shift of finite type) is a set of maps to some finite alphabet that is defined by a finite number of disallowed finite words.
By simple I mean has a small alphabet and a small number of ...
3
votes
2
answers
174
views
a bound for Feldman's **f-bar** $\bar{f}$ metric for measures
My question regards properties of the f-bar metric $\bar{f}$ defined for shift invariant measures on $\mathscr{A}^\infty$
where $\mathscr{A}$ is a finite alphabet. The definition of the $\bar{f}$ ...
- 330
7
votes
1
answer
231
views
When do automorphisms of subshifts extend to automorphisms of the full shift?
Let $A$ be a finite alphabet, $X$ = $(A^\mathbb{Z}, \sigma)$ the full shift, and $Y \subset X$ a subshift.
Question:
Are there any general results characterizing whether automorphisms of $(Y, \sigma)$...
CommunityBot
- 1
14
votes
2
answers
2k
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 ...
- 21
0
votes
2
answers
809
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 \...
- 307
2
votes
1
answer
232
views
Reference for one-sided subshifts
A well known result in Symbolic Dynamics asserts that every two-sided subshift on a finite alphabet necessarily consists of all doubly infinite words not containing any finite word from a given set of ...
- 2,263
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 ...
CommunityBot
- 1
3
votes
0
answers
209
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$...
- 2,560
3
votes
2
answers
340
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,658
1
vote
0
answers
139
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-* ...
- 105k
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$ ...
- 424
0
votes
0
answers
143
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 ...
- 1,594
0
votes
0
answers
182
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 $...
- 63.9k
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 ...
CommunityBot
- 1
0
votes
1
answer
172
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 ...
CommunityBot
- 1
2
votes
1
answer
267
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}$ ...
CommunityBot
- 1
4
votes
2
answers
445
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,459
5
votes
1
answer
543
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 ...
- 2,244
1
vote
1
answer
410
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, ...
3
votes
2
answers
717
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 ...
CommunityBot
- 1
1
vote
1
answer
171
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 ...
- 2,135
6
votes
3
answers
319
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 ...
- 18.7k
2
votes
1
answer
261
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 ...
- 201
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 ...
CommunityBot
- 1