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 $$\Sigma_{Q}:=\{x=(x_{i})_{i\in \mathbb{Z}} : x_{i}\in \{1,...,k\} \hspace{0.2cm}\textrm{and} \hspace{0.1cm}Q_{x_{i}, x_{i+1}}=1 \hspace{0.2cm}\textrm{for all}\hspace{0.1cm}i\in \mathbb{Z}\}.$$

It is known $\Sigma_{Q}$ is compact and $T$-invariant. We denote by $\mathcal{L}$ the set of admissible words. We also denote by $\mathcal{L}_{n}$ the set of admissible words with length $n.$

Denote $X:=\cup_{i=1}^{m} \mathcal{L}_{i}$ for some $m \in \mathbb{N}.$ Is $T':X^{\mathbb{Z}} \to X^{\mathbb{Z}}$ a two sided subshift of finite type?If so, what is the relation between $T$ and $T'$?

  • $\begingroup$ If I understand you correctly, this is a special case of a so-called renewal system (concatenations of words from a finite set). These are always sofic. For $X$ the golden mean shift and $m =2$ I think you get a proper sofic shift in your construction. I don't think there is any simple correspondence with $X$. $\endgroup$
    – Ville Salo
    Jun 8, 2022 at 14:03
  • $\begingroup$ @VilleSalo: Thank you very much for your comment. Do you know whether I can find a nice formula for $T'$? and a stupid question; is $X^{\mathbb{Z}}$ compact and $T$- invaraint? $\endgroup$
    – Adam
    Jun 8, 2022 at 14:09
  • $\begingroup$ It is compact and shift-invariant, indeed it's a subshift which is a factor of a subshift of finite type (a.k.a. sofic). I don't know what kind of formula you want, but to prove soficity you can make a graph with a cycle for each generating word (intersecting in a single central vertex) and label them by the generating words. Sofics are equivalently the sets of bi-infinite labels of paths in a finite graph. $\endgroup$
    – Ville Salo
    Jun 8, 2022 at 14:14
  • $\begingroup$ @VilleSalo: Thank you very much! $\endgroup$
    – Adam
    Jun 8, 2022 at 14:31
  • $\begingroup$ Btw by $X$ above I actually meant $\Sigma_Q$, but perhaps you understood anyway. $\endgroup$
    – Ville Salo
    Jun 8, 2022 at 14:53

1 Answer 1


So, I probably did not initially understand you correctly. Let me analyze four interpretations of your construction; the first is what I thought first, the second gives something uninteresting, the third gives something uninteresting, the fourth is now my best guess of what you meant (you may want to jump there first to check). Definitions of words used can be found in [1].

Interpretation 1.

We take $X$ to be the words of exactly length $n$ rather than words of length up to $n$, and by $X^{\mathbb{Z}}$ we mean all concatenations of words from $X$ in the usual sense of formal language theory. This is what I guessed at first, but this interpretation is quite unlikely to be what you mean, because it is simply not what you wrote. With this interpretation your question contains a (slightly) nontrivial mathematical problem, which is probably why I initially guessed this one. I rewrite slightly more carefully (and more correctly) what I wrote in the comments.

In this interpretation, you take $X^{\mathbb{Z}}$ to mean all $x \in \{1,\ldots,k\}^{\mathbb{Z}}$ such that for some $P \subset \mathbb{Z}$, and choices $w_p \in X$ for $p \in P$, you have for $p<q$ consecutive in $P$ that the length $|w_p| = |q - p|$, and $x_{p+i} = (w_p)_i$ for $i < |w_p|$ (where the word $w_p$ is indexed starting from $0$). So literally concatenations of words from $X$ (but you can't tell where words start!)

With this interpretation, what we get is that $X^{\mathbb{Z}}$ is a renewal system (just by definition; the definition of a renewal system is you take any finite set of words $X$ and consider $X^{\mathbb{Z}}$ in the above sense).

In general, renewal systems are always sofic (meaning factors of subshifts of finite type, equivalently sets of labels of bi-infinite paths in edge-labeled finite directed graphs), and they are topologically mixing.

They need not in general be of finite type, and indeed in you construction, you can get a proper sofic one. Namely, if $\Sigma_Q$ is the golden mean shift meaning it comes from the matrix $Q = \left(\begin{smallmatrix} 1 & 1 \\ 1 & 0 \end{smallmatrix}\right)$ as a vertex shift (what you refer to as a subshift of finite type is usually called a vertex shift), setting $m = 2$ we would get $X = \{11, 12, 21\}$, and now for all $n$, $X^{\mathbb{Z}}$ has admissible word $12211^{2n}1221$ but not $12211^{2n+1}1221$, so it is not of a subshift of finite type.

You can get a "formula" for the renewal system easily in the sense that there is a simple algorithm that produces a presentation. Of course $X$ itself is a reasonable presentation of a renewal system, but to get it in a form that more explicitly represents a sofic shift, just take a graph where $|X|$ cycles of length $m$ intersect in a single vertex, and edge-label the $i$th cycle by the $i$th word in $X$. (You can then simplify this presentation if you like.)

(If you insist on representing sofic shifts as matrices, I think there are things to say about that but I'll stop here.)

Interpretation 2.

We take the same interpretation of $X^{\mathbb{Z}}$, but $X$ is what you wrote, i.e. words up to length $m$. This interpretation doesn't give anything interesting: $X^{\mathbb{Z}}$ is equal to $A^{\mathbb{Z}}$ where $A = \{w \in X \;|\; |w| = 1\}$. I.e. it's just a full shift over the alphabet $\{1,\ldots,k\}$ (or a subset of that in case $Q$ was not essential).

Interpretation 3.

You take $X^{\mathbb{Z}}$ to just mean $A^{\mathbb{Z}}$ where the alphabet $A$ happens to be the set $X$, so the action of $T'$ shifts "by one word" on each time step. Then $X^{\mathbb{Z}}$ is just the full shift on $|X|$ letters.

Interpretation 4.

We take $X$ to be what you wrote (so words up to length $m$), but we take $X^{\mathbb{Z}}$ to mean "marked" concatenations, so e.g. let's say the letters in $Q$ are "lowercase", and define $Y$ as $X$ but capitalizing each word. So e.g. in the golden mean example with $m = 2$, renaming the letters as $a = 1, b = 2$, we would have $X = \{a, b, aa, ab, ba\}$ and $Y = \{A, B, Aa, Ab, Ba\}$. (If you don't find the capitalization natural, you can also imagine markers (of length zero) between the words.) Then take $X^{\mathbb{Z}}$ to mean $Y^{\mathbb{Z}}$ (and then that is interpreted as in Interpretation 1, i.e. as the set of bi-infinite concatenations).

This $Y^{\mathbb{Z}}$ is always a topologically mixing subshift of finite type (now subshift of finite type is in the general sense that it's defined by a finite set of forbidden words), and there is a rather simple formula for it.

First of all, its isomorphism type (up to topological conjugacy) is completely determined by how many words of length $n$ there are in $\Sigma_Q$: you can tell where words start and you can tell them apart, so you can just as well rename them to be "word 1 of length 1, word 2 of length 1, ..., word $i$ of length $n$, ...". Let $N_n$ be the number of words of length $n$.

So now, $X^{\mathbb{Z}}$ is, up to conjugacy, obtained by simply taking $N_n$ cycles of length $n$ that meet in a single vertex, and taking (unlabeled!) bi-infinite paths in that graph. In the polynomial matrix presentation explained at least in [2], you can represent this very compactly: it is simply the the $1$-by-$1$ matrix with the unique entry $\sum_{n = 1}^m N_n t^n$. In this representation, $t^n$ represents a path of length $n$ between two vertices, and in our case we just want to have paths loop around a single vertex. I didn't try to work out nice formula for an vertex/edge shift presentation in terms of $Q$, there might be a very simple formula for that too. (It is explained in [2] how a polynomial matrix is turned into an edge or vertex shift, but you don't necessarily get what you'd call a "formula" for the resulting integer matrix.)

(Side note: If we used edge shifts instead of vertex shifts there is a very nice formula for $N_i$; not sure there is one with vertex shifts. In the edge shift presentation, $Q$ is a $k$-by-$k$ matrix over natural number entries ($\mathbb{N} = 0,1,2,\ldots$), and gives rise to a graph with $k$ vertices and $Q_{a,b}$ edges from vertex $a$ to vertex $b$, and $\Sigma_Q$ is just the bi-infinite paths in this graph. Now the number of admissible words of length $n$ is simply $N_n = |Q^n|_1$, the $1$-norm = sum of entries in the graph. Edge shifts are the same as vertex shifts are the same as general subshifts of finite type up to topological conjugacy, but I don't know if you can exactly mimic the word counts of a vertex shift with an edge shift; all edge shifts can directly be seen as vertex shifts, but not vice versa.)

[1] Lind, Douglas; Marcus, Brian, An introduction to symbolic dynamics and coding, ZBL07279890.

[2] Boyle, M.; Wagoner, J. B., Positive algebraic (K)-theory and shifts of finite type, Brin, Michael (ed.) et al., Modern dynamical systems and applications. Dedicated to Anatole Katok on his 60th birthday. Cambridge: Cambridge University Press (ISBN 0-521-84073-2/hbk). 45-66 (2004). ZBL1148.37303.


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.