Abhängigkeitsbeziehung

In der Informatik , insbesondere in der Nebenläufigkeitstheorie , ist eine Abhängigkeitsrelation eine symmetrische und reflexive ^{[ 1 ] : 6} binäre Relation auf einem endlichen Definitionsbereich ; ^{[ 1 ] : 4 d.} h. eine Relation mit endlicher Toleranz . Das heißt, sie ist eine endliche Menge geordneter Paare , sodass ${\displaystyle \Sigma }$${\displaystyle D}$

• Wenn dann (symmetrisch)${\displaystyle (a,b)\in D}$${\displaystyle (b,a)\in D}$
• Wenn , dann (reflexiv)${\displaystyle a\in \Sigma }$${\displaystyle (a,a)\in D}$

Im Allgemeinen sind Abhängigkeitsrelationen nicht transitiv ; sie verallgemeinern somit den Begriff der Äquivalenzrelation, indem sie die Transitivität außer Acht lassen.

${\displaystyle \Sigma }$wird auch als das Alphabet bezeichnet , auf dem definiert ist. Die durch induzierte Unabhängigkeit ist die binäre Relation${\displaystyle D}$${\displaystyle D}$${\displaystyle I}$

${\displaystyle I=(\Sigma \times \Sigma )\setminus D}$

Das heißt, die Unabhängigkeit ist die Menge aller geordneten Paare, die nicht in liegen . Die Unabhängigkeitsrelation ist symmetrisch und irreflexiv. Umgekehrt gilt: Für jede symmetrische und irreflexive Relation auf einem endlichen Alphabet ist die Relation ${\displaystyle D}$${\displaystyle I}$

${\displaystyle D=(\Sigma \times \Sigma )\setminus I}$

ist eine Abhängigkeitsbeziehung.

Das Paar wird als konkurrentes Alphabet bezeichnet . ^{[ 2 ] : 6} Das Paar wird als Unabhängigkeitsalphabet oder Abhängigkeitsalphabet bezeichnet , wobei dieser Begriff sich auch auf das Tripel (mit induziert durch ) beziehen kann. ^{[ 3 ] : 6} Elemente heißen abhängig, wenn gilt, und unabhängig , andernfalls (d. h. wenn gilt). ^{[ 1 ] : 6} ${\displaystyle (\Sigma ,D)}$${\displaystyle (\Sigma ,I)}$${\displaystyle (\Sigma ,D,I)}$${\displaystyle I}$${\displaystyle D}$${\displaystyle x,y\in \Sigma }$${\displaystyle xDy}$${\displaystyle xIy}$

Gegeben ein Relianzalphabet , lässt sich auf dem freien Monoid aller möglichen Zeichenketten endlicher Länge eine symmetrische und irreflexive Relation definieren durch: für alle Zeichenketten und alle unabhängigen Symbole . Der Äquivalenzabschluss von wird mit oder bezeichnet und als -Äquivalenz bezeichnet. Informell gilt , wenn die Zeichenkette durch eine endliche Folge von Vertauschungen benachbarter unabhängiger Symbole in transformiert werden kann . Die Äquivalenzklassen von werden Spuren genannt [ ^{1 ] : 7–8} und sind Gegenstand ^der Spurentheorie . ${\displaystyle (\Sigma ,D,I)}$${\displaystyle \doteq }$${\displaystyle \Sigma ^{*}}$${\displaystyle xaby\doteq xbay}$${\displaystyle x,y\in \Sigma ^{*}}$${\displaystyle a,b\in I}$${\displaystyle \doteq }$${\displaystyle \equiv }$${\displaystyle \equiv _{(\Sigma ,D,I)}}$${\displaystyle (\Sigma ,D,I)}$${\displaystyle p\equiv q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle \equiv }$

Bei gegebenem Alphabet ist eine mögliche Abhängigkeitsrelation , siehe Abbildung. ${\displaystyle \Sigma =\{a,b,c\}}$${\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}}$

Die entsprechende Unabhängigkeit ist . Dann sind beispielsweise die Symbole voneinander unabhängig und beispielsweise voneinander abhängig. Die Zeichenkette ist äquivalent zu und zu , aber zu keiner anderen Zeichenkette. ${\displaystyle I=\{(b,c),\,(c,b)\}}$${\displaystyle b,c}$${\displaystyle a,b}$${\displaystyle acbba}$${\displaystyle abcba}$${\displaystyle abbca}$