Symbolsequenz

Symbolsequenzen werden in der Disziplin der symbolischen Dynamik mit Methoden der formalen Sprachen (Grammatiktheorie, Automatentheorie, Komplexitätstheorie) und der Statistik (stochastische Prozesse) untersucht.

Eine Symbolsequenz ist eine

1. endliche,
2. einseitig-unendliche oder
3. zweiseitig-unendliche

Folge von Symbolen, d.h. von Elementen aus einer endlichen Menge, dem Alphabet $\mathbf {A}$. Die Menge aller endlich aber beliebig langen Symbolsequenzen aus $\mathbf {A}$, die Kleen'sche Hülle, wird mit $\mathbf {A} ^{*}$ bezeichnet. Im Fall (1) haben die Symbolsequenzen eine feste endliche Länge $n$, und die Menge der Symbolsequenzen ist $\mathbf {A} ^{n}$. Im Fall (2) lassen sich die Symbolsequenzen als Funktionen von $\mathbb {N} \to \mathbf {A}$ auffassen, was zu der Schreibweise $\mathbf {A} ^{\mathbb {N} }$ führt. Im allgemeinsten Fall (3) sind Symbolsequenzen Funktionen von $\mathbb {Z} \to \mathbf {A}$ und die Menge aller Sequenzen wird $\mathbf {A} ^{\mathbb {Z} }$ geschrieben.

In den Fällen (2) und (3) wird die symbolische Dynamik, die den Mengen $\mathbb {N} \to \mathbf {A}$, bzw. $\mathbf {A} ^{\mathbb {Z} }$ entspricht, als voller Shift (engl.: full shift) bezeichnet. Wenn nur Teilmengen dieser Mengen in einer symbolischen Dynamik auftreten, spricht man von subshifts. Ein subshift of finite type liegt dann vor, wenn vom full shift lediglich eine endliche Menge verbotener Symbolsequenzen auszuschließen ist. In diesem Fall können die Symbolsequenzen von einem endlichen Automaten erzeugt werden.