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
416
views
Fast algorithms for external angle computations
Two related problems related to the complex quadratic polynomial $f_c(z) = z^2 + c$ and Mandelbrot and/or Julia sets:
find an external angle $\theta_c$ for a complex point $c$
find a complex point $...
- 111
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 ...
- 1,706
3
votes
0
answers
74
views
Second eigenvalue of primitive matrix
Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$.
The ...
- 143
3
votes
0
answers
125
views
Description of Anderson-Putnam CW-complex construction
I have been trying to read the paper, Topological invariants fo substitution tiling and their associated $C^*$-algebras, to learn more about a construction of Anderson-Putnam complexes. However, it ...
- 633
3
votes
0
answers
81
views
Confusion on the assumption when discussing the kneading invariants for unimodal maps
A unimodal map is a continuous map $f:[0,1]\longrightarrow [0,1]$ such that there is only one turning point (critical point), denoted by $c$, and $f(0)=f(1)=0$.
Unimodal map is related to kneading ...
- 131
3
votes
0
answers
78
views
Example of primitive substitution with two rationally independent eigenvalues?
I am looking for an example of a primitive substitution $\sigma$, not Pisot, such that the associated subshift $X_\sigma$ has two irrational and rationally independent eigenvalues. Equivalently, a ...
- 31
3
votes
0
answers
72
views
Does an asymptotic component with large size in a minimal subshift always exist?
Let $(X, T)$ be a minimal subshift, i.e. $X$ is a closed $T$-invariant subset of $A^\mathbb{Z}$, where $T$ is the shift. A pair $x,y\in X$ is asymptotic if $d(T^nx, T^ny)$ goes to zero as $n\to\infty$....
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
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
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
2
votes
1
answer
323
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?
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
1
answer
238
views
Invariant measure of geodesic flow on unit tangent bundle of a modular surface
This is a paper written by Series "THE MODULAR SURFACE AND CONTINUED FRACTIONS".
I want to know about above construction natural invariant measure $\mu$ for the geodesic flow on $T_{1}M$ ...
- 73
2
votes
1
answer
131
views
Morse-Hedlund\Coven-Hedlund theorem for non-Abelian groups
There is a well know theorem by Coven and Hedlund, in Sequences with minimal block growth, stating that the complexity function of an aperiodic sequence\configuration $\omega\in \mathcal{A}^{\mathbb{Z}...
- 633
2
votes
1
answer
205
views
Exponential mixing for subshifts
I asked this question on Math.StackExchange some time ago and got no responses.
Let $G=(V,E)$ be a finite graph with adjacency matrix $A$. Let us consider the associated subshift of finite type
$$
\...
- 151
2
votes
1
answer
214
views
Irrational rotations are rank 2 by intervals without spacers
Let $\alpha$ be an irrational number, and $R_\alpha$ be the rotation by $\alpha$, that is $R_\alpha(x)=x+\alpha\bmod 1$.
S. Ferenczi in his survey [Systems of finite rank. Colloq. Math. 73 (1997), no. ...
- 1,658
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}$ ...
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
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
2
votes
1
answer
183
views
A sensitive 2-dimensional cellular automaton with a blocking word
I'am a Ph.D student in the domain of discrete dynamical systems. My thesis is about spectral properties of cellular automata in higher dimension.
Kurka gives a classification for one dimensional ...
2
votes
1
answer
129
views
Reference on relation between SFTs and Wang-tiles
I've been looking at several papers which allude to a relation between SFTs. Namely, given an SFT $\Omega \subseteq \mathcal{A}^{\mathbb{Z}^2}$ with allowed patches $\mathcal{F}$, we can associate a ...
- 633
2
votes
1
answer
143
views
Search for a general formula from known iterative relation
$F$ is a mapping among $\{\theta_{n_1n_2}\}$, with $\eta_{1/2}$ being arbitrary constants involved.
$F: \theta_{n_1n_2} \rightarrow \theta_{n_1+1n_2}+\theta_{n_1n_2+1}+\eta_{1}n_1\theta_{n_{1}-1n_{2}} ...
- 23
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 ...
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{...
- 5,590
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
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 ...
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 ...
2
votes
1
answer
181
views
Union of admissible words are subshift of finite type
Assume that $Q=(q_{ij})$ is a $k\times k$ with $q_{ij}\in \{0, 1\}.$ The two side subshift of finite type associated to the matrix $Q$ is a left shift map $T:\Sigma_{Q}\rightarrow \Sigma_{Q}$, where
...
- 1,043
2
votes
3
answers
639
views
The critical exponent function
It is a known fact [1] that, for every $c\in (1,\infty]$, it is possible to find a finite alphabet $\mathcal{A}$ and a word $w\in \mathcal{A}^\omega$ such that $w$ has critical exponent $c$. It looks ...
- 4,459
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
0
answers
92
views
Conjugacy between piecewise linear circle maps
Let $\mathcal{M}$ the Mandelbrot set,
$\mathcal{M}=\{c \in \mathbb{C}: \{Q_c^n(0) \}_{n \in \mathbb{N}} \text{ is bounded, where } Q_c(z)=z^2+c \}$
And let the hyperbolic or stable component, $H_n=\{ ...
- 271
2
votes
1
answer
269
views
Chaotic dynamics of maps on unit square that are NOT Triangular
We will denote the compact interval $[0,1]$ by $I$ and the unit square $[0,1]\times[0,1]$ by $I^2$. Triangular map on $I^2$ is a continuous map $F:I^2\to I^2$ of the form $F(x,y)=(f(x),g(x,y))$ where $...
- 271
2
votes
0
answers
116
views
Aperiodic SFT equal to a substitution subshift
I was wondering whether there are primitive symbolic substitutions over $\mathbb{Z}^d$ and alphabet $\mathcal{A}$ whose associated subshift is equal to an aperiodic SFT. By SFT here I mean a subshift ...
- 633
2
votes
1
answer
89
views
Lower bounds for pattern complexity of linearly repetitive aperiodic subshifts
I recently asked in this thread about lower bounds on the complexity in the case where we have an aperiodic subshift. If I denote $c_n(\Omega)$ as the number of possible patterns on $Q_n=\{0,...,n−1\}^...
- 633
2
votes
0
answers
116
views
Birth of chaos due to nonautonomous perturbation
Let $\sigma, b>0$. I want to study the dynamics of the map
$$ T \colon \mathbb{N} \times \mathbb{S}^1 \times \mathbb{R} \to \mathbb{S}^1 \times \mathbb{R}$$ such that
$$T_{\sigma,b}(n,\theta,y) = (\...
2
votes
0
answers
79
views
When is replacing the prefix of an angled internal address a valid operation?
While working on an artwork exploring patterns in the Mandelbrot set fractal, I constructed an angled internal address by:
$$
1 \overset{1/2}\longrightarrow 2 \overset{1/2}\longrightarrow 3 \overset{1/...
- 111
2
votes
0
answers
77
views
Equivalence between Gibbs measures and conformal measures
I was reading an article about Gibbs measures, but the author defines Gibbs measures in a different way than the usual (which is done by using conditional expectations). The way that he defines I have ...
- 151
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
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
1
vote
1
answer
148
views
Approximation of subshifts in Hausdorff distance
I have recently been interested in some questions which stem from taking subshifts which converge to a limiting subshift in the Hausdorff metric.
More specifically, given an alphabet $\mathcal{A}$, I ...
- 633
1
vote
1
answer
155
views
Properties of limit set for cellular automata
Is anyone familiar with results about properties of the limit set of the local rule for a cellular automaton? I haven't been able to find any good materials on the subject from an initial search, and ...
- 633
1
vote
1
answer
74
views
Computing admissible patches of a substitution
I have been recently trying to look at substitution tilings with finite local complexity by examining their admissible patch\pattern atlas, which is sometimes called their language. I have also seen ...
- 633
1
vote
1
answer
192
views
Topological full groups of subshifts: differences between one-dimensional and multi-dimensional subshifts
For a multidimensional subshift $X$ over $\mathbb Z^d$, the topological full group $[X]$ is the set of homeomorphisms $f$ of $X$ that can be written as $f : x \mapsto \sigma_{c(x)}(x)$ with $c : X \to ...
- 113
1
vote
2
answers
232
views
What does the extension theorem for tilings state?
I have seen several references to the so-called Extension Theorem in the context of tilings of Euclidean space.
E.g. in "The Local Theorem for Monotypic Tilings" one reads
The Extension Theorem [......
- 13.6k
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 ...
- 8,493
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}.$
...
- 1,805
1
vote
1
answer
139
views
A special kind of pseudo-garden eden states in cellular automata
I'm currently investigating Wolfram's elementary cellular automata on finite grids with periodic boundary conditions, i.e. on $\mathbb{Z}/k$ for different $k$.
It is clear that for each rule $R$ and ...
- 9,730
1
vote
1
answer
162
views
Properties of Følner sequences for countably infinite, finitely generated, amenable, periodic/torsion groups
I've managed to prove certain things about a class of groups, and the only remaining class of groups are those specified in the title. I'm mainly studying symbolic dynamics and not group theory, so I'...
- 119
1
vote
1
answer
88
views
Example of connected factor of symbolic system that is not a rotation
I am looking for an example of a factor $f\colon (X,T) \to (Y,T)$ between topological dynamical systems, where $(X,T)$ is a minimal subshift and $Y$ a connected topological space such that $(Y,T)$ is ...
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