I was looking at the following exercise from Lind/Marcus book An Introduction to Symbolic Dynamics and Coding that I cannot solve. Can someone give me a hint?

Find an example of a pair of irreducible sofic shifts $X,Y$ and a sliding block code $f:X\rightarrow Y$ such that $f$ is not one-to-one, but the restriction of f to periodic points is one-to-one.

The exercise points to other exercises that I also don't know.

Let $X$ be an irreducible shift of finite type and $f:X\rightarrow Y$ a sliding block code. Prove that $f$ is an embedding if and only if it is one-to-one on the periodic points of $X$.

I know the definitions for sofic, finite type, irreducible and sliding block code; but have no idea how to use them. Why things should be different here for sofic shifts and shifts of finite type?

  • $\begingroup$ Glossary: a "sliding block code" is just a continuous equivariant map $f$, i.e., such that $f\circ s_X=s_Y\circ f$ where $s_X$ and $s_Y$ are the shift maps. $\endgroup$
    – YCor
    Mar 31, 2020 at 8:29

1 Answer 1


This is a fun pair of exercises (the first one you mention is 3.2.9 and the second is 2.3.6a)! For 2.3.6a, recode to a $1$-block code $\phi$ on an irreducible edge shift $X$, suppose that $x, x' \in X$ are such that $x \neq x'$ but $\phi(x) = \phi(x')$. Consider two cases: either $x_j \neq x_j'$ for either all $j > i$ or all $j < i$; or there exist $j < i < k$ with $x_j = x_j'$, $x_k = x_k'$. In either case, try to construct a pair of distinct periodic points whose images agree.

Then, for 3.2.9, here's an idea for a construction: try to construct a sofic shift $X$ by labelling an irreducible graph with alphabet $\{ 0, 1, 2 \}$, such that the path presenting $10^m 1$ can be determined by whether $m$ is even or odd, and such that every cycle (other than self-loops) contains a $2$. Then code from $X$ to $Y$ by replacing $2$ by $1$ and leaving the other symbols the same.

EDIT: I've provided an answer because I didn't notice I was on MO rather than Math.SE, but this question should probably be on Math.SE rather than MO. It's an exercise in an introductory textbook, albeit a textbook with some rather tricky exercises.

  • 4
    $\begingroup$ "Tricky"? I'd call them "instructive". $\endgroup$ Mar 31, 2020 at 12:19

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.