Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Subshift of finite type
Summary
In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine. The most widely studied shift spaces are the subshifts of finite type.
Let V be a finite set of n symbols (alphabet). Let X denote the set V^\Z of all bi-infinite sequences of elements of V together with the shift operator T. We endow V with the discrete topology and X with the product topology. A symbolic flow or subshift is a closed T-invariant subset Y of X and the associated language LY is the set of finite subsequences of Y.
Now let A be an n × n adjacency matrix with entries in {0, 1}. Using these elements we construct a directed graph G = (V, E) with V the set of vertices and E the set of edges containing the directed edge x → y in E if and only if A_x, y = 1. Let Y be the set of all infinite admissible sequences of edges, where by admissible it is meant that the sequence is a walk of the graph, and the sequence can be either one-sided or two-sided infinite. Let T be the left shift operator on such sequences; it plays the role of the time-evolution operator of the dynamical system. A subshift of finite type is then defined as a pair (Y, T) obtained in this way. If the sequence extends to infinity in only one direction, it is called a one-sided subshift of finite type, and if it is bilateral, it is called a two-sided subshift of finite type.
Formally, one may define the sequences of edges as
This is the space of all sequences of symbols such that the symbol p can be followed by the symbol q only if the (p, q)-th entry of the matrix A is 1. The space of all bi-infinite sequences is defined analogously:
The shift operator T maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e.
Clearly this map is only invertible in the case of the two-sided shift.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.