On the Shannon Cover of Shifts of Finite Type

D. P. B. Chaves, C. Pimentel, B. F. Uchôa-Filho

DOI: 10.14209/sbrt.2003.277

Evento: XX Simpósio Brasileiro de Telecomunicações (SBrT2003)

Keywords: Constrained sequences labeled Shannon cover symbolic dynamics sofic shifts

Abstract

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.

Download