The Chain Relation in Sofic Subshifts

Article type: Research Article

Authors: Kazda, Alexandr

Affiliations: Department of Algebra, MFF UK Sokolovská 83, Praha 8, 186 75, Czech Republic. E-mail: [email protected]

Note: [] Address for correspondence: Department of Algebra, MFF UK, Sokolovská' 83, Praha 8, 186 75, Czech Republic

Abstract: The paper gives a characterisation of the chain relation of a sofic subshift. Every sofic subshift Σ can be described by a labelled graph G. Factorising G in a suitable way we obtain the graph G/≈ that offers insight into some properties of the original subshift. Using G/≈ we describe first the chain relation in Σ, 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.

Keywords: Sofic subshift, chain relation, chain-transitivity, chain-mixing, attractor

Journal: Fundamenta Informaticae, vol. 84, no. 3-4, pp. 375-390, 2008