On the Shannon Cover of Shifts of Finite Type

A shift space is a collection of sequences of symbols from a finite alphabet satisfying certain constraints. A shift of finite type is a shift whose constraints can be represented by a finite list of forbidden blocks. Every shift of finite type can also be represented by a labeled directed graph that has the property that every biinfinite walk on the graph generates an allowed sequence by reading off the labels of its edges. It is both of theoretical and practical interest to find the minimal graph (called the Shannon cover), i.e., the one with the fewest vertices, presenting a shift of finite type. The main contribution of this paper is an efficient iterative vertex-minimization algorithm that considers the higher edge graph as the initial graph.