Algorithmic Approach to Devaney Chaos in Shift Spaces

• Autorzy: Oprocha P.
• Języki publikacji: EN

Abstrakty

EN

Among the class of sofic shifts Devaney chaos is equivalent to topological transitivity. The aim of this paper is to study possibilities of detection of this phenomena when a right-resolving graph presentation of a sofic shift is given. We show that Devaney chaos detection is co-NP-hard problem and point out some possible improvements of algorithms known from the literature.

Słowa kluczowe

EN

Devaney chaos; sofic shift; symbolic dynamics; irreducible shift space; graph; complexity; NP-completness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 3-4
• Strony: 435--446
• Opis fizyczny: bibliogr. 12 poz.

Twórcy

autor

Oprocha P.

• Faculty of Applied Mathematics, AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krak´ow, Poland,

Bibliografia

• [1] N. Aoki and K. Hiraide. Topological theory of dynamical systems, volume 52 of North-HollandMathematical Library. North-Holland Publishing Co., Amsterdam, 1994. Recent advances.
• [2] J. Banks, J. Brooks, G. Cairns, G. Davis, and P. Stacey. On Devaney's definition of chaos. Amer. Math. Monthly, 99(4):332-334, 1992.
• [3] M.-P. B'eal and D. Perrin. Symbolic dynamics and finite automata. In Handbook of formal languages, Vol. 2, pages 463-505. Springer, Berlin, 1997.
• [4] D. Beauquier. Minimal automaton for a factorial, transitive, and rational language. Theoret. Comput. Sci., 67(1):65-73, 1989.
• [5] M. Boyle, B. Kitchens, and B. Marcus. A note on minimal covers for sofic systems. Proc. Amer. Math. Soc., 95(3):403-411, 1985.
• [6] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to algorithms. TheMIT Electrical Engineering and Computer Science Series. MIT Press, Cambridge, MA, 1990.
• [7] R. L. Devaney. An introduction to chaotic dynamical systems. Addison-Wesley Studies in Nonlinearity. Addison-Wesley Publishing Company Advanced Book Program, Redwood City, CA, second edition, 1989.
• [8] N. Jonoska. Sofic shifts with synchronizing presentations. Theoret. Comput. Sci., 158(1-2):81-115, 1996.
• [9] J. Kwapisz. Cocyclic subshifts. Math. Z., 234(2):255-290, 2000.
• [10] D. Lind and B. Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995.
• [11] R. Mañé. Ergodic theory and differentiable dynamics, volume 8 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1987. Translated from the Portuguese by Silvio Levy.
• [12] P. Oprocha and P.Wilczy´nski. Shift spaces and distributional chaos. Chaos Solitons Fractals, 31(2):347-355, 2007.