Symbolsequenz

Symbolsequenz

Symbolsequenzen werden in der Disziplin der symbolischen Dynamik mit Methoden der Formalen Sprachen (Grammatiktheorie, Automatentheorie, Komplexitätstheorie) und der Theorie Stochastischer 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, die Alphabet \mathbf{A} genannt wird. Die Menge aller endlich aber beliebig langen Symbolsequenzen aus \mathbf{A}, die Kleenesche Hülle, wird mit \mathbf{A}^* bezeichnet.

Im Fall (1) haben die Symbolsequenzen eine feste endliche Länge n und werden als Wort bzw. Block der Länge n bezeichnet. Die Menge der Wörter der Länge n ist \mathbf{A}^n. Solche Symbolsequenzen heißen in der Programmierung auch Zeichenketten oder engl. Strings.

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 \mathbf{A}^\mathbb{N}, 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 eine Menge verbotener Symbolsequenzen auszuschließen ist, die lediglich eine endliche Menge von Wörtern fester Länge n enthalten. In diesem Fall können die Symbolsequenzen von einem endlichen Automaten erzeugt werden.


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Symbolische Dynamik — Die Symbolische Dynamik ist ein Zweig der Theorie dynamischer Systeme, in dem Methoden der Formalen Sprachen (Grammatiktheorie, Automatentheorie, Komplexitätstheorie) und der Theorie stochastischer Prozesse zur Anwendung kommen. Der Ausgangspunkt …   Deutsch Wikipedia

  • Backward-Algorithmus — Der Backward Algorithmus (auch Rückwärts Algorithmus, Rückwärts Prozedur) berechnet die Wahrscheinlichkeit, dass bei einem gegebenen Hidden Markov Modell M und einer beobachteten Symbolsequenz m das Modell sich zur Zeit i in dem Zustand s befand …   Deutsch Wikipedia

  • Berlekamp-Massey-Algorithmus — Der Berlekamp Massey Algorithmus (nach Elwyn Berlekamp und James Massey) dient dazu, das kürzeste, lineare rückgekoppelte Schieberegister zu finden, das eine gegebene Folge von Symbolen ausgibt. Die Symbole können aus einem beliebigen Körper… …   Deutsch Wikipedia

  • DNS-Sequenzanalyse — Eine DNA Sequenzanalyse ist in der Molekularbiologie und Bioinformatik die automatisierte, computergestützte Bestimmung von charakteristischen Abschnitten, insbesondere Genen, auf einer DNA Sequenz. Untersucht werden die bei der DNA Sequenzierung …   Deutsch Wikipedia

  • Edit-Distanz — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… …   Deutsch Wikipedia

  • Editierdistanz — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… …   Deutsch Wikipedia

  • Levenshtein-Abstand — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… …   Deutsch Wikipedia

  • Levenstein-Distanz — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… …   Deutsch Wikipedia

  • Lewenstein-Distanz — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… …   Deutsch Wikipedia

  • Run-Test — Der Run oder Runs Test (auch Wald Wolfowitz Test, nach Abraham Wald und Jacob Wolfowitz, Iterationstest oder Geary Test) ist ein nichtparametrischer Test auf Zufälligkeit einer Folge. Ausgegangen wird von einem Urnenmodell mit zwei Sorten Kugeln… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”