A survey on transitivity in discrete time dynamical systems. Application to symbolic systems and related languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 333-352.

The main goal of this paper is the investigation of a relevant property which appears in the various definition of deterministic topological chaos for discrete time dynamical system: transitivity. Starting from the standard Devaney's notion of topological chaos based on regularity, transitivity, and sensitivity to the initial conditions, the critique formulated by Knudsen is taken into account in order to exclude periodic chaos from this definition. Transitivity (or some stronger versions of it) turns out to be the relevant condition of chaos and its role is discussed by a survey of some important results about it with the presentation of some new results. In particular, we study topological mixing, strong transitivity, and full transitivity. Their applications to symbolic dynamics are investigated with respect to the relationships with the associated languages.

DOI : 10.1051/ita:2006016
Classification : 37B05, 37B10
Mots-clés : transitivity, chaos, symbolic dynamics, formal languages 
@article{ITA_2006__40_2_333_0,
     author = {Cattaneo, Gianpiero and Dennunzio, Alberto and Farina, Fabio},
     title = {A survey on transitivity in discrete time dynamical systems. {Application} to symbolic systems and related languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {333--352},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {2},
     year = {2006},
     doi = {10.1051/ita:2006016},
     mrnumber = {2252643},
     zbl = {1112.37005},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2006016/}
}
TY  - JOUR
AU  - Cattaneo, Gianpiero
AU  - Dennunzio, Alberto
AU  - Farina, Fabio
TI  - A survey on transitivity in discrete time dynamical systems. Application to symbolic systems and related languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 333
EP  - 352
VL  - 40
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006016/
DO  - 10.1051/ita:2006016
LA  - en
ID  - ITA_2006__40_2_333_0
ER  - 
%0 Journal Article
%A Cattaneo, Gianpiero
%A Dennunzio, Alberto
%A Farina, Fabio
%T A survey on transitivity in discrete time dynamical systems. Application to symbolic systems and related languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 333-352
%V 40
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2006016/
%R 10.1051/ita:2006016
%G en
%F ITA_2006__40_2_333_0
Cattaneo, Gianpiero; Dennunzio, Alberto; Farina, Fabio. A survey on transitivity in discrete time dynamical systems. Application to symbolic systems and related languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 333-352. doi : 10.1051/ita:2006016. http://www.numdam.org/articles/10.1051/ita:2006016/

[1] E. Akin, The general topology of dynamical systems. Graduate Stud. Math. 1, American Mathematical Society, Providence (1993). | MR | Zbl

[2] E. Akin and S. Kolyada, Li-Yorke sensitivity. Nonlinearity 16 (2003) 1421-1433. | MR | Zbl

[3] L.L. Alseda, S. Kolyada, J. Llibre and L. Snoha, Entropy and periodic points for transitive maps. Trans. Amer. Math. Soc. 351 (1999) 1551-1573. | MR | Zbl

[4] L.L. Alseda, M.A. Del Rio and J.A. Rodriguez, A survey on the relation between transitivity and dense periodicity for graph maps. J. Diff. Equ. Appl. 9 (2003) 281-288. | MR | Zbl

[5] J. Banks, J. Brooks, G. Cairns, G. Davis and P. Stacey, On Devaney's definition of chaos. Amer. Math. Montly 99 (1992) 332-334. | MR | Zbl

[6] F. Blanchard and G. Hansel, Languages and subshifts, Automata on Infinite Words (Berlin), edited by M. Nivat and D. Perrin. Lect. Notes Comput. Sci. 192 (1985) 138-146. | MR | Zbl

[7] F. Blanchard, P. Kurka and A. Maas, Topological and measure-theoretic properties of one-dimensional cellular automata. Physica D 103 (1997) 86-99. | MR | Zbl

[8] F. Blanchard and P. Tisseur, Some properties of cellular automata with equicontinuity points, Ann. Inst. Henri Poincaré. Probab. Statist. 36 (2000) 569-582. | EuDML | Numdam | MR | Zbl

[9] M. Boyle and B. Kitchens, Periodic points for cellular automata. Indag. Math. 10 (1999) 483-493. | MR | Zbl

[10] G. Cattaneo and A. Dennunzio, Subshift behavior of cellular automata. topological properties and related languages, Machines, Computations, and Universality, in 4th International Conference, MCU 2004 (Berlin). Lect. Notes Comput. Sci. 3354 (2005) 140-152. | Zbl

[11] G. Cattaneo, A. Dennunzio and L. Margara, Chaotic subshifts and related languages applications to one-dimensional cellular automata. Fundamenta Informaticae 52 (2002) 39-80. | Zbl

[12] G. Cattaneo, A. Dennunzio and L. Margara, Solution of some conjectures about topological properties of linear cellular automata. Theoret. Comput. Sci. 325 (2004) 249-271. | Zbl

[13] G. Cattaneo, E. Formenti and L. Margara, Topological definitions of deterministic chaos, applications to cellular automata dynamics, in Cellular Automata, a Parallel Model, edited by M. Delorme and J. Mazoyer. Kluwer Academic Pub., Dordrecht. Math. Appl. 460 (1999) 213-259.

[14] B. Codenotti and L. Margara, Transitive cellular automata are sensitive. Amer. Math. Monthly 103 (1996) 58-62. | Zbl

[15] A. Crannell, The role of transitivity in Devaney's definition of chaos. Amer. Math. Monthly 102 (1995) 768-793. | Zbl

[16] M. Denker, C. Grillenberger and K. Sigmund, Ergodic theory on compact spaces. Lect. Notes Math. 527 (1976). | MR | Zbl

[17] R.L. Devaney, An introduction to chaotic dynamical systems. Second ed., Addison-Wesley (1989). | MR | Zbl

[18] J.-P. Eckmann and D. Ruelle, Ergodic theory of chaos and strange attractors. Rev. Mod. Phys. 57 (1985) 617-656. | Zbl

[19] E. Glasner and B. Weiss, Sensitive dependence on initial condition. Nonlinearity 6 (1993) 1067-1075. | Zbl

[20] A. Kameyama, Topological transitivity and strong transitivity. Acta Math. Univ. Comenianae LXXI, 139. | MR | Zbl

[21] V. Kannan and A. Nagar, Topological transitivity for discrete dynamical systems, in Applicable Mathematics in Golden Age, edited by J.C. Misra. Narosa Pub. (2002).

[22] A. Katok and B. Hasselblatt, Introduction to the modern theory of dynamical systems. Cambridge University Press (1995). | MR | Zbl

[23] J.L. Kelley, General topology. Springer-Verlag (1975). | MR | Zbl

[24] C. Knudsen, Chaos without nonperiodicity. Amer. Math. Monthly 101 (1994) 563-565. | Zbl

[25] S. Kolyada, Li-Yorke sensitivity and other concepts of chaos. Ukrainian Mathematical Journal 56 (2004) 1242-1257. | Zbl

[26] S. Kolyada and L. Snoha, Some aspect of topological transitivity - a survey. Grazer Math. Ber. 334 (1997) 3-35. | Zbl

[27] P. Kurka, Topological and symbolic dynamics, Cours Spécialisés 11. Société Mathématique de France (2004). | MR | Zbl

[28] J.P. Lasalle, Stability theory for difference equations. MAA Studies in Math., American Mathematical Society (1976). | MR

[29] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding. Cambidge University Press (1995). | MR | Zbl

[30] S. Martinez, Hyperbolic dynamical systems with isolated points. Lect. Notes Math. 527 (1983) 47-64.

[31] W. Parry, Intrinsic markov chains. Trans. Amer. Math. Soc. 112 (1964) 55-56. | Zbl

[32] D. Ruelle, Strange attractors. Math. Intell. 2 (1980) 126-137. | Zbl

[33] Bau sen Du, On the nature of chaos, arXiv:math.DS/0602585 v1 (February 2006). | MR

[34] S. Silverman, On maps with dense orbits and the definitions of chaos. Rocky Mountain Jour. Math. 22 (1992) 353-375. | Zbl

[35] M. Vellekoop and R. Berglund, On intervals, transitivity = chaos. Amer. Math. Monthly 101 (1994) 353-355. | Zbl

[36] P. Walters, An introduction to ergodic theory. Springer, Berlin (1982). | MR | Zbl

[37] B. Weiss, Topological transitivity and ergodic measures. Math. Syst. Theory 5 (1971) 71-5. | Zbl

[38] S. Wiggins, Global bifurcations and chaos. Springer, Berlin (1988). | MR | Zbl

Cité par Sources :