Formal languages in dynamical systems. (English) Zbl 0857.58025

Summary: 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 formal language in a natural way. 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 which additionally maps topological conjugacies between subshifts to generalized sequential machines between languages. The Chomsky hierarchy measuring the complexity of formal languages can be transferred via this functor to the symbolic dynamics and proves to be a conjugacy invariant. 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. Required concepts and definitions are repeated, so that this article is essentially self-contained.


37B99 Topological dynamics
68Q80 Cellular automata (computational aspects)
37E99 Low-dimensional dynamical systems
Full Text: arXiv EuDML