Math 2.0

Dynamical systems and ergodic theory Definition

Subshift of finite type

Builds on Shift spaceProduct topology

Definition

Let AA be a finite set, called the alphabet. Let AℤA^{\Z} be the set of all sequences x=(xi)i∈ℤx = (x_i)_{i \in \Z} with xi∈Ax_i \in A, with the product topology of the discrete topologies. Let σ ⁣:Aℤ→Aℤ\sigma \colon A^{\Z} \to A^{\Z} be the shift map, σ(x)i=xi+1\sigma(x)_i = x_{i+1}. A word w=w1⋯wnw = w_1 \cdots w_n over AA occurs in xx if xi+1⋯xi+n=wx_{i+1} \cdots x_{i+n} = w for some i∈ℤi \in \Z. For a set FF of words, let XFX_F be the set of all x∈Aℤx \in A^{\Z} in which no word of FF occurs. A subset X⊆AℤX \subseteq A^{\Z} is a subshift of finite type if X=XFX = X_F for some finite set FF of words.

Remarks

Each XFX_F is closed and satisfies σ(XF)=XF\sigma(X_F) = X_F, so it is a shift space. Example: the golden mean shift is XFX_F with A={0,1}A = \set{0, 1} and F={11}F = \set{11}. It is a subshift of finite type because FF is finite. Non-example: the even shift is the set of x∈{0,1}ℤx \in \set{0,1}^{\Z} in which between any two 11s there is an even number of 00s. It is a shift space, but it is not of finite type. Each word 102n+111 0^{2n+1} 1 is forbidden, while all its proper subwords occur in allowed sequences, so no finite list of forbidden words can exclude all of them. Every subshift of finite type is conjugate to a vertex shift. Given a finite set BB and a square 00-11 matrix MM indexed by BB, this is the set of x∈Bℤx \in B^{\Z} with Mxixi+1=1M_{x_i x_{i+1}} = 1 for all ii. The same definition with AℤdA^{\Z^d} and finite forbidden patterns gives the multidimensional subshifts of finite type.

Reading path

To understand this page from the ground up, read these 22 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionProposition, concept, no evidence levelPropositionconceptShift space, concept, no evidence levelShift spaceconceptSet, definition, no evidence levelSetdefinitionConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionEmpty set, object, no evidence levelEmpty setobjectFamily of sets, definition, no evidence levelFamily of setsdefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionIntersection, definition, no evidence levelIntersectiondefinitionUnion, definition, no evidence levelUniondefinitionExistential quantifier, definition, no evidence levelExistential quantifierdefinitionUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionCartesian product, definition, no evidence levelCartesian productdefinitionSubset, definition, no evidence levelSubsetdefinitionUnion of a family of sets, definition, no evidence levelUnion of a family of …definitionTopological space, definition, no evidence levelTopological spacedefinitionBasis of a topology, definition, no evidence levelBasis of a topologydefinitionProduct topology, definition, no evidence levelProduct topologydefinitionSubshift of finite type, definition, no evidence levelSubshift of finite ty…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. Proposition concept
  3. Shift space concept
  4. Set definition
  5. Conjunction definition
  6. Disjunction definition
  7. Implication definition
  8. Predicate definition
  9. Empty set object
  10. Family of sets definition
  11. Ordered pair definition
  12. Intersection definition
  13. Union definition
  14. Existential quantifier definition
  15. Universal quantifier definition
  16. Cartesian product definition
  17. Subset definition
  18. Union of a family of sets definition
  19. Topological space definition
  20. Basis of a topology definition
  21. Product topology definition
  22. Subshift of finite type definition

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Subshift_of_finite_type
About this page
TagM7RPDE39FM
URIm2://M7RPDE39FM
Kinddefinition
WritingW0 stub
MSC37B10
DefinesSubshift of finite type
UsesShift space, Product topology

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by