The Chain Relation in Sofic Subshifts

• Autorzy: Kazda A.
• Języki publikacji: EN

Abstrakty

EN

The paper gives a characterisation of the chain relation of a sofic subshift. Every sofic subshift S 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 [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.

Słowa kluczowe

EN

sofic subshift; chain relation; chain-transitivity; chain-mixing; attractor

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 3-4
• Strony: 375--390
• Opis fizyczny: bibliogr. 6 poz., wykr.

Twórcy

autor

Kazda A.

• Department of Algebra, MFF UK, Sokolovska 83, Praha 8, 186 75, czech Republilc,

Bibliografia

• [1] Cormen, H. T., Leiserson, E. C, Rivest, L. R.: Introduction to Algorithms, The MIT Press, Cambridge, 1999.
• [2] Formenti, E., Kurka, P.: Subshift Attractors of Cellular Automata, Nonlinearity, 20(1), 2007,105-117.
• [3] Jarvis, J. P., Shier, D. R.: Applied Mathematical Modeling: A Multidisciplinary Approach, chapter Graph Theoretic Analysis of Finite Markov Chains, CRC Press, Boca Raton, 1999.
• [4] Kurka, P.: Topological and symbolic dynamics, Societe Mathematique de France, Paris, 2003.
• [5] Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.
• [61 Oprocha,P.: Algorithmic approach to Devaney chaos in shift spaces, Fundamenta Informaticae.