A survey on transitivity in discrete time dynamical systems. application to symbolic systems and related languages
---
paper_title: Ergodic theory of chaos and strange attractors

paper_content:

Physical and numerical experiments show that deterministic noise, or chaos, is ubiquitous. While a good understanding of the onset of chaos has been achieved, using as a mathematical tool the geometric theory of differentiable dynamical systems, moderately excited chaotic systems require new tools, which are provided by the ergodic theory of dynamical systems. This theory has reached a stage where fruitful contact and exchange with physical experiments has become widespread. The present review is an account of the main mathematical ideas and their concrete implementation in analyzing experiments. The main subjects are the theory of dimensions (number of excited degrees of freedom), entropy (production of information), and characteristic exponents (describing sensitivity to initial conditions). The relations between these quantities, as well as their experimental determination, are discussed. The systematic investigation of these quantities provides us for the first time with a reasonable understanding of dynamical systems, excited well beyond the quasiperiodic regimes. This is another step towards understanding highly turbulent fluids.
---
paper_title: On Devaney's Definition of Chaos

paper_content:

Chaotic dynamical systems have received a great deal of attention in recent years (see for instance [2], [3]). Although there has been no universally accepted mathematical definition of chaos, the popular text by Devaney [1] isolates three components as being the essential features of chaos. They are formulated for a continuous map f: X -> X on some metric space X (to avoid degenerate cases we will assume in this note that X is not a finite set). The first of Devaney's three conditions is that f is transitive; that is, for all non-empty open subsets U and V of X there exists a natural number k such that f k(U) n V is nonempty. In a certain sense, transitivity is an irreducibility condition. The second of Devaney's conditions is that the periodic points of f form a dense subset of X. Devaney refers to this condition as an "element of regularity" ([1], p. 50). The final condition is called sensitive dependence on initial conditions; f verifies this property if there is a positive real number 8 (a sensitivity constant) such that for every point x in X and every neighborhood N of x there exists a point y in N and a nonnegative integer n such that the nth iterates fW(x) and ff(y) of x and y respectively, are more than distance 8 apart. This sensitivity condition captures the idea that in chaotic systems minute errors in experimental readings eventually lead to large scale divergence. Sensitive dependence on initial conditions is thus widely understood as being the central idea in chaos.
---
paper_title: Topological and measure-theoretic properties of one-dimensional cellular automata

paper_content:

Abstract This is a survey of known results and open questions about the topological and ergodic dynamics of one-dimensional cellular automata.
---
paper_title: Transitive Cellular Automata Are Sensitive

paper_content:

The notion of chaos is a very appealing one, and it has intrigued several scientists (see [1, 2, 5, 7] for some work on the properties that characterize a chaotic process). There are simple deterministic dynamical systems that exhibit unpredictable behavior. Though counter-intuitive, this fact has a very clear eEplanation. The lack of infinite precision causes a loss of information which is dramatic for some processes which quickly lose their deterministic nature to assume a non deterministic (unpredictable) one. This observation leads to the intuition that investigations about chaos are intrinsically of an interdisciplinary nature. Indeed, the study of chaos draws its deeper methods of analysis from mathematics, it owes to physics a treasure of important problems, and it brings challenges to the science of computing. The reason for this last fact relies on the above observation that a chaotic behavior lies in between two different modes of computation, determinism and nondeterminism, whose quantitative comparison is central to the main open questions in the theory of computing [6]. A chaotic phenomenon can indeed be viewed as a deterministic one, in the presence of infinite precision, and as a nondeterministic one, in the presence of finite precision constraints (see Figure 1). Thus one should look at chaotic processes as at processes merged into time, space, and precision bounds, which are the key resources in the science of computing.
---
paper_title: Chaotic Subshifts and Related Languages Applications to one-dimensional Cellular Automata

paper_content:

Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.
---
paper_title: Solution of some conjectures about topological properties of linear cellular automata

paper_content:

We study two dynamical properties of linear D-dimensional cellular automata over Zm namely, denseness of periodic points and topological mixing. For what concerns denseness of periodic points, we complete the work initiated in (Theoret. Comput. Sci. 174 (1997) 157, Theoret. Comput. Sci. 233 (1-2) (2000) 147, 14th Annual Symp. on Theoretical Aspects of Computer Science (STACS '97), LNCS n. 1200, Springer, Berlin, 1997, pp. 427-438) by proving that a linear cellular automata has dense periodic points over the entire space of configurations if and only if it is surjective (as conjectured in (Cattaneo et al., 2000)). For non-surjective linear CA we give a complete characterization of the subspace where periodic points are dense. For what concerns topological mixing, we prove that this property is equivalent to transitivity and then easily checkable. Finally, we classify linear cellular automata according to the definition of chaos given by Devaney in (An Introduction to Chaotic Dynamical Systems, 2nd ed., Addison-Wesley, Reading, MA, USA, 1989).
---
paper_title: Ergodic Theory on Compact Spaces

paper_content:

Measure-theoretic dynamical systems.- Measures on compact metric spaces.- Invariant measures for continuous tranformations.- Time averages.- Ergodicity.- Mixing and transitivity.- Shifts and subshifts.- Measures on the shift space.- Partitions and generators.- Information and entropy.- The computation of entropy.- Entropy for Bernoulli and Markov shifts.- Ergodic decompositions.- Topological entropy.- Topological generators.- Expansive homeomorphisms.- Subshifts of finite type.- The variational principle for topological entropy.- Measures with maximal entropy-Intrinsically ergodic systems.- Entropy-Expansive homeomorphisms.- The specification property.- Specification and expansiveness.- Basic sets for axiom A.- Automorphisms of the torus.- More on subshifts of finite type.- Preparations for generator theorems.- Combinatorial construction of minimal sets.- Finite generators for ergodic transformations (theorem of Krieger).- Strictly ergodic embedding (Theorem of Jewett and Krieger).- Finite generators for aperiodic transformations.- Embedding theorems for aperiodic transformations.
---
paper_title: An Introduction to Symbolic Dynamics and Coding

paper_content:

From the Publisher: ::: Although it originated as a method to study general dynamical systems, symbolic dynamics is useful in coding for data storage and transmission as well as in linear algebra. Requiring only a undergraduate knowledge of linear algebra, this first general textbook includes over 500 exercises.
---
paper_title: LI-Yorke sensitivity and other concepts of chaos

paper_content:

We give a survey of the theory of chaos for topological dynamical systems defined by continuous maps on compact metric spaces.
---
paper_title: Transitive Cellular Automata Are Sensitive

paper_content:

The notion of chaos is a very appealing one, and it has intrigued several scientists (see [1, 2, 5, 7] for some work on the properties that characterize a chaotic process). There are simple deterministic dynamical systems that exhibit unpredictable behavior. Though counter-intuitive, this fact has a very clear eEplanation. The lack of infinite precision causes a loss of information which is dramatic for some processes which quickly lose their deterministic nature to assume a non deterministic (unpredictable) one. This observation leads to the intuition that investigations about chaos are intrinsically of an interdisciplinary nature. Indeed, the study of chaos draws its deeper methods of analysis from mathematics, it owes to physics a treasure of important problems, and it brings challenges to the science of computing. The reason for this last fact relies on the above observation that a chaotic behavior lies in between two different modes of computation, determinism and nondeterminism, whose quantitative comparison is central to the main open questions in the theory of computing [6]. A chaotic phenomenon can indeed be viewed as a deterministic one, in the presence of infinite precision, and as a nondeterministic one, in the presence of finite precision constraints (see Figure 1). Thus one should look at chaotic processes as at processes merged into time, space, and precision bounds, which are the key resources in the science of computing.
---
paper_title: Topological and measure-theoretic properties of one-dimensional cellular automata

paper_content:

Abstract This is a survey of known results and open questions about the topological and ergodic dynamics of one-dimensional cellular automata.
---
paper_title: Sensitive dependence on initial conditions

paper_content:

It is shown that the property of sensitive dependence on initial conditions in the sense of Guckenheimer follows from the other two more technical parts of one of the most common recent definitions of chaotic systems. It follows that this definition applies to a broad range of dynamical systems, many of which should not be considered chaotic. We investigate the implications of sensitive dependence on initial conditions and its relation to dynamical properties such as rigidity, ergodicity, minimality and positive topological entropy. In light of these investigations and several examples which we exhibit, we propose a natural family of dynamical systems- chi -systems-as a better abstract framework for a general theory of chaotic dynamics.
---
paper_title: Chaotic Subshifts and Related Languages Applications to one-dimensional Cellular Automata

paper_content:

Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.
---
paper_title: Chaotic Subshifts and Related Languages Applications to one-dimensional Cellular Automata

paper_content:

Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.
---
paper_title: TOPOLOGICAL TRANSITIVITY AND STRONG TRANSITIVITY

paper_content:

The system herein includes light optic means which functions as a light beam distributor in making available, almost instantly, an information bearing beam of light along any one of a plurality of differently positioned output paths stemming from the system as opposed to the conventional or more well known line scan beam deflection systems.
---
paper_title: Ergodic Theory on Compact Spaces

paper_content:

Measure-theoretic dynamical systems.- Measures on compact metric spaces.- Invariant measures for continuous tranformations.- Time averages.- Ergodicity.- Mixing and transitivity.- Shifts and subshifts.- Measures on the shift space.- Partitions and generators.- Information and entropy.- The computation of entropy.- Entropy for Bernoulli and Markov shifts.- Ergodic decompositions.- Topological entropy.- Topological generators.- Expansive homeomorphisms.- Subshifts of finite type.- The variational principle for topological entropy.- Measures with maximal entropy-Intrinsically ergodic systems.- Entropy-Expansive homeomorphisms.- The specification property.- Specification and expansiveness.- Basic sets for axiom A.- Automorphisms of the torus.- More on subshifts of finite type.- Preparations for generator theorems.- Combinatorial construction of minimal sets.- Finite generators for ergodic transformations (theorem of Krieger).- Strictly ergodic embedding (Theorem of Jewett and Krieger).- Finite generators for aperiodic transformations.- Embedding theorems for aperiodic transformations.
---
paper_title: Ergodic Theory on Compact Spaces

paper_content:

Measure-theoretic dynamical systems.- Measures on compact metric spaces.- Invariant measures for continuous tranformations.- Time averages.- Ergodicity.- Mixing and transitivity.- Shifts and subshifts.- Measures on the shift space.- Partitions and generators.- Information and entropy.- The computation of entropy.- Entropy for Bernoulli and Markov shifts.- Ergodic decompositions.- Topological entropy.- Topological generators.- Expansive homeomorphisms.- Subshifts of finite type.- The variational principle for topological entropy.- Measures with maximal entropy-Intrinsically ergodic systems.- Entropy-Expansive homeomorphisms.- The specification property.- Specification and expansiveness.- Basic sets for axiom A.- Automorphisms of the torus.- More on subshifts of finite type.- Preparations for generator theorems.- Combinatorial construction of minimal sets.- Finite generators for ergodic transformations (theorem of Krieger).- Strictly ergodic embedding (Theorem of Jewett and Krieger).- Finite generators for aperiodic transformations.- Embedding theorems for aperiodic transformations.
---
paper_title: Chaotic Subshifts and Related Languages Applications to one-dimensional Cellular Automata

paper_content:

Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.
---
paper_title: An Introduction to Symbolic Dynamics and Coding

paper_content:

From the Publisher: ::: Although it originated as a method to study general dynamical systems, symbolic dynamics is useful in coding for data storage and transmission as well as in linear algebra. Requiring only a undergraduate knowledge of linear algebra, this first general textbook includes over 500 exercises.
---
paper_title: Hyperbolic dynamical systems with isolated points

paper_content:

We prove that the non-wandering set of an hyperbolic topologically transitive dynamical system whose basis space is an infinite non perfect set, is the union of two disjoint orbits.
---

Title: A survey on transitivity in discrete time dynamical systems. Application to symbolic systems and related languages

Section 1: Introduction
Description 1: This section provides an introduction to discrete time dynamical systems (DTDS), including their formal definition, main properties, and their relevance to the study of chaos.

Section 2: Positive Transitivity
Description 2: This section defines the notion of positive transitivity in DTDS, explores its significance, and presents relevant examples and propositions.

Section 3: Mixing Condition
Description 3: This section introduces the concept of topological mixing for DTDS, discussing its properties, implications, and its relation to sensitivity.

Section 4: Strong Transitivity and Minimality
Description 4: This section discusses strong transitivity and its connections to minimality, including important theorems and examples distinguishing these notions from the positive transitivity.

Section 5: Subshifts and Related Languages
Description 5: This section explores subshifts over a finite alphabet, associated symbolic languages, and their use in understanding the dynamics of DTDS. It includes definitions and examples of subshifts of finite type (SFT).

Section 6: Conclusion
Description 6: This section summarizes the findings of the survey, highlighting the different definitions of transitivity, their interrelationships, and their implications for the study of chaos in DTDS.