imported>Aka: Punkt hinter Abkürzung gesetzt, Kleinkram

2020-04-18T15:14:19Z

Punkt hinter Abkürzung gesetzt, Kleinkram

Neue Seite

In der [[Theoretische Informatik|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 <math>\Sigma</math> ein Alphabet und <math> D \subseteq \Sigma \times \Sigma </math> eine binäre, symmetrische und reflexive Relation auf <math>\Sigma</math>, Abhängigekeitsrelation genannt. Man sagt <math> a </math> und <math> b </math> sind unabhängig, falls <math> (a,b) \not\in D </math>.

Dann definiert man <math> \sim_D </math> als die kleinste [[Äquivalenzrelation]], für die gilt

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

Die Äquivalenzklassen von <math> \Sigma^* </math> unter <math>\sim_D</math> sind als Mazurkiewicz spuren bekannt.

Da <math> \sim_D </math> eine [[Kongruenzrelation]] unter der [[Konkatenation (Formale Sprache)|Konkatenation]] ist, bildet <math> \Sigma^*_{/ \sim_D} </math> einen Monoid, der als <math> \mathbb{M}(\Sigma, D) </math> notiert wird, den Monoid der Spuren.

Teilmengen von <math> \mathbb{M} </math> werden dann als Spursprachen bezeichnet.

== Erkennbarkeit ==
Spezielle Spursprachen lassen sich, wie formale Sprachen, durch Automaten erkennen. Dabei finden Asynchrone [[Zellulärer Automat|Zelluläre Automaten]] Verwendung.

[[Kategorie:Theorie formaler Sprachen]]

Spursprache - Versionsgeschichte

imported>Aka: Punkt hinter Abkürzung gesetzt, Kleinkram