Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

In der Theoretischen Informatik versteht man unter einer Spursprache eine Formale Sprache, die parallel ausführbare Prozesse modelliert. Dabei werden die Buchstaben eines gegebenen Alphabets als elementare Operationen betrachtet, die sich in ihrer Ausführung untereinander beeinflussen (d.h. sie sind abhängig) oder unabhängig voneinander sein können. Ein Wort in dieser Sprache entspricht dann dem hintereinanderausführen dieser Operationen, also einem Programm. Zwei Wörter über diesem Alphabet (also zwei Programme) gelten dann als ununterscheidbar , wenn sich nur durch (evtl mehrmaliges) vertauschen nebeneinanderstehender, unabhängiger Buchstaben ineinander überführen lassen, also letztlich den gleichen Algorithmus beschreiben.

Definition

Sei Σ ein Alphabet und eine binäre, symmetrische und reflexive Relation auf Σ, Abhängigekeitsrelation genannt. Man sagt a und b sind unabhängig, falls .

Dann definiert man als die kleinste Äquivalenzrelation, für die gilt

für alle .

Die Äquivalenzklassen von Σ ^* unter sind als Mazurkiewicz spuren bekannt.

Da eine Kongruenzrelation unter der Konkatenation ist, bildet einen Monoid, der als notiert wird, den Monoid der Spuren.

Teilmengen von werden dann als Spursprachen bezeichnet

Erkennbarkeit

Spezielle Spursprachen lassen sich, wie formale Sprachen, durch Automaten erkennen. Dabei finden Asynchrone Zelluläre Automaten verwendung

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Spursprache, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.