Shifts of finite type obtained by forbidding a single pattern

Given a finite word $ w $, Guibas and Odlyzko (J. Combin. Theory Ser. A, 30, 1981,183-208) showed that the autocorrelation polynomial $ \phi_w(t) $ of $ w $, which records the set of self-overlaps of $ w $, explicitly determines for each $ n $, the number $ |\mathcal{B}_n(w)| $ of words of length $ n $ that avoid $ w $. We consider this and related problems from the viewpoint of symbolic dynamics, focusing on the setting of $ X_{\{w\}} $, the space of all bi-infinite sequences that avoid $ w $. We first summarize and elaborate upon (J. Combin. Theory Ser. A, 30, 1981,183-208) and other work to show that the sequence $ |\mathcal{B}_n(w)| $ is equivalent to several invariants of $ X_{\{w\}} $. We then give a finite-state labeled graphical representation $ L_w $ of $ X_{\{w\}} $ and show that $ w $ can be recovered from the graph isomorphism class of the unlabeled version of $ L_w $. Using $ L_w $, we apply ideas from probability and Perron-Frobenius theory to obtain results comparing features of $ X_{\{w\}} $ for different $ w $. Next, we give partial results on the problem of classifying the spaces $ X_{\{w\}} $ up to conjugacy. Finally, we extend some of our results to spaces of multi-dimensional arrays that avoid a given finite pattern.