Spursprache

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 sie 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 $D \subseteq \Sigma \times \Sigma$ eine binäre, symmetrische und reflexive Relation auf Σ, Abhängigekeitsrelation genannt. Man sagt a und b sind unabhängig, falls $(a,b) \not\in D$.

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

$xaby \sim_D xbay \iff (a,b) \not\in D$ für alle $x,y \in \Sigma^*, a,b \in \Sigma$.

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

Da ∼_D eine Kongruenzrelation unter der Konkatenation ist, bildet $\Sigma^*_{/ \sim_D}$ einen Monoid, der als $\mathbb{M}(\Sigma, D)$ notiert wird, den Monoid der Spuren.

Teilmengen von $\mathbb{M}$ werden dann als Spursprachen bezeichnet.

Erkennbarkeit

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