The chain relation in sofic subshifts

Abstract

The paper gives a characterisation of the chain relation of a sofic subshift. Every sofic subshift $\Sigma$ can be described by a labelled graph $G$. Factorising $G$ in a suitable way we obtain the graph $G{/}_{\approx }$ that offers insight into some properties of the original subshift. Using $G{/}_{\approx }$ we describe first the chain relation in $\Sigma$, then characterise chain-transitive sofic subshifts, chain-mixing sofic subshifts and finally the attractors of the subshift dynamic system. At the end we present (straightforward) algorithms deciding chain-transitivity and chain-mixing properties of a sofic subshift and listing all the attractors of the subshift system.

14 pages, 9 figures, preprint (final version published in Fundamenta Informaticae)