依存関係

コンピュータサイエンス、特に並行性理論において、依存関係は有限領域上の対称的かつ反射的な二項関係である^{[ 1 ] : 6}${\displaystyle \Sigma }$; ^{[ 1 ] : 4}すなわち有限許容関係。つまり、順序対の有限集合である。${\displaystyle D}$、したがって

• もし${\displaystyle (a,b)\in D}$ それから ${\displaystyle (b,a)\in D}$（対称）
• もし${\displaystyle a\in \Sigma }$、 それから ${\displaystyle (a,a)\in D}$（再帰）

一般的に、依存関係は推移的ではない。したがって、依存関係は推移性を捨てることで同値関係の概念を一般化する。

${\displaystyle \Sigma }$は、​${\displaystyle D}$定義されています。${\displaystyle D}$二項関係${\displaystyle I}$

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

つまり、独立性とは、に含まれないすべての順序対の集合である。${\displaystyle D}$独立関係は対称かつ非反射的である。逆に、任意の対称かつ非反射的な関係が与えられた場合${\displaystyle I}$有限アルファベット上での関係

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

これは依存関係です。

その二人${\displaystyle (\Sigma ,D)}$同時アルファベットと呼ばれる。^{[ 2 ]： 6}ペア${\displaystyle (\Sigma ,I)}$これは独立アルファベットまたは信頼アルファベットと呼ばれていますが、この用語はトリプルを指す場合もあります${\displaystyle (\Sigma ,D,I)}$（と${\displaystyle I}$誘発される${\displaystyle D}$). ^{[ 3 ]： 6つの}要素${\displaystyle x,y\in \Sigma }$依存的と呼ばれるのは、${\displaystyle xDy}$保持し、独立、そうでなければ（つまり、${\displaystyle xIy}$保持する）。^{[ 1 ]： 6}

信頼度アルファベットが与えられた場合${\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 }$これらはトレースと呼ばれ、^{[ 1 ] : 7-8}でトレース理論で研究されています。

アルファベットが与えられた${\displaystyle \Sigma =\{a,b,c\}}$考えられる依存関係は${\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}}$写真をご覧ください。

対応する独立性は${\displaystyle I=\{(b,c),\,(c,b)\}}$すると、例えば記号が${\displaystyle b,c}$互いに独立しており、例えば${\displaystyle a,b}$依存しています。文字列${\displaystyle acbba}$と同等${\displaystyle abcba}$そして${\displaystyle abbca}$ただし、他の文字列には対応していません。