Formal Languages in Dynamical Systems
| dc.creator | Troll, G. | |
| dc.date | 1993-05-21 | |
| dc.date.accessioned | 2026-07-07T09:07:37Z | |
| dc.date.available | 2026-07-07T09:07:37Z | |
| dc.description | 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. | |
| dc.description | 23 pages, LaTeX | |
| dc.identifier | https://arxiv.org/abs/chao-dyn/9305008 | |
| dc.identifier | http://arxiv.org/abs/chao-dyn/9305008 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/150434 | |
| dc.subject | Chaotic Dynamics | |
| dc.subject | Adaptation and Self-Organizing Systems | |
| dc.title | Formal Languages in Dynamical Systems | |
| dc.type | text |