Nonlinear Sciences – Adaptation and Self-Organizing Systems
Scientific paper
1993-05-21
Nonlinear Sciences
Adaptation and Self-Organizing Systems
23 pages, LaTeX
Scientific paper
We treat here the interrelation between formal languages and those dynamical systems that can be described by cellular automata (CA). There is a well-known injective map which identifies any CA-invariant subshift with a central formal language. However, in the special case of a symbolic dynamics, i.e. where the CA is just the shift map, one gets a stronger result: the identification map can be extended to a functor between the categories of symbolic dynamics and formal languages. This functor additionally maps topological conjugacies between subshifts to empty-string-limited generalized sequential machines between languages. If the periodic points form a dense set, a case which arises in a commonly used notion of chaotic dynamics, then an even more natural map to assign a formal language to a subshift is offered. This map extends to a functor, too. The Chomsky hierarchy measuring the complexity of formal languages can be transferred via either of these functors from formal languages to symbolic dynamics and proves to be a conjugacy invariant there. In this way it acquires a dynamical meaning. After reviewing some results of the complexity of CA-invariant subshifts, special attention is given to a new kind of invariant subshift: the trapped set, which originates from the theory of chaotic scattering and for which one can study complexity transitions.
No associations
LandOfFree
Formal Languages in Dynamical Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Formal Languages in Dynamical Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Formal Languages in Dynamical Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-168806