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

Bearbeiten

Sei   ein Alphabet und   eine binäre, symmetrische und reflexive Relation auf  , Abhängigekeitsrelation genannt. Man sagt   und   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

Bearbeiten

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