Enumeration of subwords on sequences and its applications

Abstract: We start with an enumeration problem studied by Guibas and Odlyzko in 1979 and its applications in seemingly unrelated scenarios that includes game theory, pattern matching algorithm, graph theory and symbolic dynamics. One of the main objects of our study is a subshift of finite type, which is used as a tool to model a large class of dynamical systems. It consists of collection of all one-sided sequences over a finite symbol set which contain none of a given finite collection of words. We discuss its correspondence with an edge labeled multigraph and hence with its associated adjacency matrix. We see how some (topological as well as measure theoretic) properties of a subshift of finite type are studied using this correspondence and solve a generalized version of the enumeration problem.