2
$\begingroup$

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/science/article/pii/0304397586901088)] is a shift space $X$ which admits a cover (a presentation) by a countable labeled strongly connected (irreducible) directed graph $(G, g)$ where a labeling function maps the edge set of $G$ into a finite set $A$. This means that $X$ is the closure of the image of the map $L_g \colon S_G \to A^\mathbb{Z}$ induced on the countable Markov shift $S_G$ of all bi-infinite paths in G by $L_g(x)_i := g(x_i)$, $i \in \mathbb{Z}$, $x \in S_G$. In Lind and Marcus book An introduction to symbolic dynamics and coding, page 451 there are some other equivalent conditions.

A coded system is transitive by definition. 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$ is also admissible. Every transitive sofic shift is synchronized. A synchronized system is well-known to be coded. Moreover, any synchronized system admits a presentetion by a connected, right-resolving, follower separated labeled graph with a magic word (known as the Fisher cover).

It is relatively easy to prove that a synchronized system is topologically mixing if and only if there are two closed paths in its Fisher cover of relatively prime lengths. Does the same hold for coded systems? It is easy to see that two closed paths in $G$ with relatively prime lengths imply that the shift space presented by $G$ is mixing, but how about the converse? I mean, does every mixing coded system has a presentation with two closed paths of relatively prime lengths?

Note: The equivalence holds if $G$ is finite, but I am interested in the case, when $G$ may be infinite.

Edit There exists a presentation of a full shift such that every loop has even length. But there are presentations of the full shift with two closed paths of relatively prime lengths.

$\endgroup$
3
  • $\begingroup$ An equivalent charcterization of coded systems says that a shift space $X$ is a coded system if there exist a countable collection of finite words (blocks) $(w_n)_{n\in\mathbb{N}}$, called generators, such that $X$ is the closure of the set of sequences obtained by freely concatenating the generators. The question above can be then restated as follows: Does every mixing coded system have a set of genertaors $(w_n)_{n\in\mathbb{N}}$ such that $\text{gcd} \{|w_n| : n\in\mathbb{N}\}=1$? ($|w|$ is the length of a word (block) $w$). $\endgroup$ Feb 9, 2014 at 23:27
  • $\begingroup$ What does happen when you have a mixing coded system $X$ with generators $(w_n)_{n\in\mathbb{N}}$ and you add a new block w, i.e. you consider $X'$ that corresponds to the closure of the sets of sequences obtained by freely concatenating words in $(w_n)_{n\in\mathbb{N}}$ and $w$ ? Is the mixing property preserved? $\endgroup$
    – user39115
    Mar 27, 2014 at 18:54
  • $\begingroup$ Usually yes. If there are two generators with relatively prime lengths, then after adding any block the system would still be mixing. $\endgroup$ Mar 31, 2014 at 8:13

2 Answers 2

3
$\begingroup$

In general no! Let $X=\{0,\,1\}^{\mathbb{Z}}$ be the full shift generated by $\{00,\,10,\,01,\,11\}$ and set $w=12$ and let $\sigma_{X'}$ be the shift map on $X'$. Then $N(w,\,w)=\{n: {\sigma}_{X'}^nw\cap w\neq\emptyset\}=2\mathbb{N}$ and it is not a cofinite set as required for a mixing system.

$\endgroup$
1
  • $\begingroup$ But this does not answer my question. It is an answer to a question of user39115 stated in comments. I asked the following: Does there exists a mixing coded system X such that for every graph G representing X the lcd of all lengths of periods of loops in G is greater than 1? $\endgroup$ May 8, 2014 at 20:56
0
$\begingroup$

If you do not sure that $(w_n)$, the generator of mixing coded, has relatively prime lengths or there is at least one $w_i\in (w_n)$ s.t. $gcd(w_i,\,w)=1$, we can not say that the new coded system which generated by $(w_n)$ and $w$ is mixing!

$\endgroup$
1
  • $\begingroup$ Ok, but my question is about something different... $\endgroup$ May 8, 2014 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.