Jewiki unterstützen. Jewiki, die größte Online-Enzy­klo­pädie zum Judentum.

Helfen Sie Jewiki mit einer kleinen oder auch größeren Spende. Einmalig oder regelmäßig, damit die Zukunft von Jewiki gesichert bleibt ...

Vielen Dank für Ihr Engagement! (→ Spendenkonten)

How to read Jewiki in your desired language · Comment lire Jewiki dans votre langue préférée · Cómo leer Jewiki en su idioma preferido · בשפה הרצויה Jewiki כיצד לקרוא · Как читать Jewiki на предпочитаемом вами языке · كيف تقرأ Jewiki باللغة التي تريدها · Como ler o Jewiki na sua língua preferida

Spursprache

Aus Jewiki
Zur Navigation springen Zur Suche springen

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 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

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

Dieser Artikel basiert ursprünglich auf dem Artikel Spursprache aus der freien Enzyklopädie Wikipedia und steht unter der Doppellizenz GNU-Lizenz für freie Dokumentation und Creative Commons CC-BY-SA 3.0 Unported. In der Wikipedia ist eine Liste der ursprünglichen Wikipedia-Autoren verfügbar.