|
|
Sfb 288 Differential Geometry and Quantum Physics |
Abstract for Sfb Preprint No. 47
Formal Languages in Dynamical Systems G. Troll
Acta Univ. Carol., Math. Phys. 34, No.2, 117-134 (1993)
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.
No PostScript version available.