Perturbations of Shifts of Finite Type
Douglas A. Lind · SIAM Journal on Discrete Mathematics · 1989
Shifts of finite type describe the infinite trips on a labeled graph, and provide theoretical models for data storage and transmission. The consequences of forbidding a fixed word to occur, which can be considered as a small change or perturbation in the system, are investigated. This situation arises in prefix synchronized codes, where a certain prefix, used to synchronize code words, is forbidden to occur in the rest of the word. If T is the adjacency matrix of the graph, and $\lambda_T $ is its spectral radius, then forbidding a word of length k results in a drop in spectral radius that lies between two positive constants times $\lambda_T^{ - K}$. The zeta function summarizes the number of possible periodic trips. The author gives an explicit calculation of the zeta function for the resulting subshift, which involves the characteristic polynomial of T, a cofactor of $t I - T$, and the correlation polynomial of the word. A modification of the Knuth-Morris-Pratt pattern matching algorithm shows that this calculation can be done in time that is linear in the word length, answering a question of Bowen and Lanford. The structure of this correlation polynomial is used to obtain sharp bounds on the degree of the denominator of the zeta function. The Jordan form of the higher order presentations of the shift of finite type is also computed, and that of the perturbation in many cases. Most of the results were discovered experimentally with a computer.