4
$\begingroup$

I am reading some lecture notes on Dynamical Systems, and I arrived at subshifts of finite type (ssft). The professor defines $\sum_n^+$ as the set of all one-sided sequences $.s_0s_1s_2...$ where for each $i$, $s_i \in \{0, 1, 2, ..., n-1\}.$ Then, let $A$ be any $n \times n$ matrix whose entries are in $\{0, 1\}$. Then the notes define the subshift of finite type corresponding to A as

$$\{\underline{s} = s_0 s_1 s_2...|\forall i: A_{s_i, s_{i+1}} = 1\}$$

I would like to show an example to make sure I understood the definition clearly. Let $A$ be the matrix $$A = \begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 1\\ 1 & 1 & 0 \end{bmatrix}$$

I think we are supposed to label the rows as row 0, row 1, row 2, and the columns as col 0, col 1, col 2. N. We have $$1 = A_{00} = A_{01} = A_{11} = A_{12} = A_{20} = A_{21}$$ $$0 = A_{02} = A_{10} = A_{22}$$ Therefore the sequences in $\sum_A^+$ are exactly those whose size-2 blocks are on this list: $00, 01, 11, 12, 20, 21$. So for example, an element of $\sum_A^+$ is $$.00011120000000...$$ But an element not in $\sum_A^+$ is $$.000020000.....$$

Is my understanding of ssft correct? Thank you so much!

$\endgroup$
3
  • 1
    $\begingroup$ That’s how I understand it. $\endgroup$ Sep 25, 2020 at 1:57
  • $\begingroup$ @BrianM.Scott Thank you very much! $\endgroup$
    – user56202
    Sep 25, 2020 at 13:57
  • $\begingroup$ My pleasure; it was a new term for me until a couple of days ago. $\endgroup$ Sep 25, 2020 at 16:11

1 Answer 1

3
$\begingroup$

Yes, your understanding is correct. The set $\sum_n^+$ contains all one-sided infinite sequences over the alphabet $\{0, \ldots, n-1\}$. Sometimes it's useful to instead consider two-sided sequences: so the phrase "subshift of finite type", by itself, can be ambiguous. Your $\sum_A^+$ is a one-sided subshift of finite type. Also, when people say "subshift of finite type" they're usually talking about a slightly more complicated structure: not just the set of sequences, but also a particular topology on that set (namely, the one induced by the Tychonoff product topology on $\Sigma_n^+$) and a shift map $\sigma$, which slides a sequence to the left (or, in the one-sided case, deletes the first symbol: e.g., $\sigma(.121000\ldots) = .21000\ldots$).

The thing that makes it of "finite type" is that it can also be defined by a finite set of rules. An equivalent way of defining $\sum_A^+$ is to take all sequences that do not contain the forbidden words '02', '10', or '22'. If we wanted to, we could also forbid longer words like '01210'. The forbidden-words definition is more general: If we were to forbid longer words, there might not be a way of specifying the rule via a transition matrix. There is no matrix $A$ for which $\Sigma_A^+$ consists of all sequences that do not contain '01210'.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .