Subshift of finite type

Subshift of finite type (SFT) is a concept in the field of symbolic dynamics, a branch of mathematics that studies sequences of symbols with constraints. Symbolic dynamics abstracts dynamics by discretizing both time and state space, and it is closely related to the study of dynamical systems. Subshifts of finite type are particularly important in this field because they serve as a model for various physical and computational systems, and they have been extensively studied for their mathematical properties and applications.

Definition

A subshift of finite type is defined over a finite alphabet \(A\), which is a finite set of symbols. Consider \(A^{\mathbb{Z}}\) to be the set of all bi-infinite sequences of symbols from \(A\). A sequence in \(A^{\mathbb{Z}}\) can be thought of as a configuration of symbols extending infinitely in both directions along a one-dimensional lattice.

A subshift \(X \subseteq A^{\mathbb{Z}}\) is of finite type if there exists a finite set \(F\) of finite words (or blocks) over \(A\) such that \(X\) consists of all bi-infinite sequences in \(A^{\mathbb{Z}}\) that do not contain any subsequence from \(F\). The set \(F\) is often referred to as the set of forbidden words. The idea is that a subshift of finite type is defined by specifying which finite patterns are not allowed to appear in the sequences.

Properties and Examples

Subshifts of finite type have several important properties. They are topologically mixing if, for any two finite patterns that appear in sequences of the subshift, there exists a number \(N\) such that any pattern can be followed by any other pattern with at most \(N\) symbols in between, within any sequence of the subshift. This property is related to the concept of ergodicity in dynamical systems.

An example of a subshift of finite type is the golden mean shift, where the alphabet \(A = \{0, 1\}\) and the set of forbidden words \(F = \{11\}\). This means that in any sequence in the golden mean shift, the symbol '1' cannot be immediately followed by another '1'. This simple rule leads to a rich structure and interesting dynamical properties.

Applications

Subshifts of finite type are used in various areas of mathematics and applied sciences. In computer science, they are related to the theory of formal languages and automata theory. In physics, they model certain physical systems where the states of the system can be represented by symbolic sequences, and the dynamics can be captured by the shift operation and constraints on allowable sequences.

Relation to Other Concepts

Subshifts of finite type are closely related to other concepts in symbolic dynamics and dynamical systems, such as sofic shifts and cellular automata. Sofic shifts can be seen as a generalization of subshifts of finite type, where the constraints on sequences are specified by a finite automaton rather than a finite list of forbidden words.

See Also

• Symbolic dynamics
• Dynamical systems
• Ergodic theory
• Cellular automata