종속관계

컴퓨터 과학에서, 특히 동시성 이론에서, 종속관계는 유한하고 ^{[1]: 4} 대칭적이며 반사적인 이중 관계,^{[1]: 6} 즉 유한 허용관계다. 즉, 다음과 같이 정렬된 $쌍{\displaystyle }$ D ${\displaystyle D}$의 유한 집합이다$.$

• $({\displaystyle }$ ${\displaystyle a}$, ${\displaystyle b}$) ${\displaystyle \in }$ ${\displaystyle D}$ ${\displaystyle (a,b)\in D}$인 경우, (${\displaystyle b}$ ${\displaystyle ,)\in }$ ${\displaystyle D}$ ${\displaystyle (b,a)\in D}($대칭)
• ${\displaystyle a}$이(${\displaystyle 가}$) 관계가 정의된 집합의 요소인$$ 경우 ( , )${\displaystyle \in }$ ${\displaystyle D}$ ${\displaystyle$ ($a,a)\in$ D$}($가)$$

일반적으로 종속관계는 전이적 관계가 아니다. 따라서 그들은 전이성을 버림으로써 동등관계의 개념을 일반화한다.

$\sigma {\displaystyle \mathrm{}}$ ${\displaystyle \Sigma}$이(가) $D{\displaystyle }$ ${\displaystyle D}$이(가) 정의된 알파벳을 나타내는$$ 경우 D ${\displaystyle$ D$}$에 $의해{\displaystyle }$ 유도되는 독립성은 $이진{\displaystyle }$ 관계 I ${\displaystyle I}$이다.

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

즉, $독립성$은 D ${\displaystyle D}$에 없는 모든 순서 쌍들의 집합이다$.$ 독립성 관계는 대칭적이고 회복 불가능하다. 반대로, 유한한 알파벳에$$ 대칭적이고 불손한 $관계{\displaystyle }$ I ${\displaystyle I}$을(를) 부여할 경우 관계

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

의존 관계다.

쌍(${\displaystyle \mathrm{\sigma }}$,${\displaystyle D}$ ) ${\displaystyle$(\$Sigma ,D)}$을(를) 동시 알파벳이라고 한다.^{[2]: 6} (${\displaystyle \mathrm{\sigma }}$, ${\displaystyle I}$) ${\displaystyle (\Sigma ,I)}$ 쌍을 독립 알파벳 또는 의존 알파벳이라고 부르지만$$, 이 용어는 또한 3중$({\displaystyle }$ ${\displaystyle \mathrm{\sigma }}$, ${\displaystyle D}$, ${\displaystyle I}$) ${\displaystyle (\Sigma ,D,I$$)}$을($D{\displaystyle }$$$${\displaystyty$D})로 유도할$$ 수도 있다.$$^{[3]: 6} 요소 $x{\displaystyle }$, ${\displaystyle \mathrm{y}}$ ${\displaystyle \in }$ {$${ {\$displaystyle x,y$\in \$Sigma }$은(는) x Dy$${\$displaystyle$ $xDy$$}$을(를$)$ 보유할$$ 경우 종속적이라고 하며, 그렇지 않을 경우($즉{\displaystyle }$, x ${\displaystyle I}$ ${\displaystyle y}$ ${\displaysty$}을 보유할$$ 경우) 독립적이라고 한다$$.^{[1]: 6}

Given a reliance alphabet ${\displaystyle (\Sigma ,D,I)}$, a symmetric and irreflexive relation ${\displaystyle \doteq }$ can be defined on the free monoid ${\displaystyle \Sigma ^{*}}$ of all possible strings of finite length by: ${\displaystyle xaby\doteq xbay}$ for all strings $$${\displaystyle {\mathrm{}}^{}}$, ${\displaystyle y}$ ${\displaystyle \in }$ ${\displaystyle {\ast }^{}}$ ${\$ 및 모든$$ ${\displaystyle \mathrm{독립}}$ 기호${\displaystyle }a{\displaystyle }$ , b ${\displaystyle \in }$ ${\displaystyle I}$ ${\displaystyle a,b\in I$ The equivalence closure of ${\displaystyle \doteq }$ is denoted ${\displaystyle \equiv }$ or ${\displaystyle \equiv _{(\Sigma ,D,I)}}$ and called ${\displaystyle (\Sigma ,D,I)}$-equivalence. 비공식적으로 p${\displaystyle }p{\displaystyle }$ ${\displaystyle q}$ ${\displaystyle p\equiv q$$}$은(는$)$ $문자열$ p {\$displaystyle$ p}을(를) 인접한 독립 기호의 유한 순서 스왑에 의해$$ $q{\displaystyle }$ ${\displaystyle q}($으)로 변환할$$ 수 있는 경우 고정한다$$. $\equiv {\displaystyle }$ ${\displaystyle \equiv }$의 동등성 클래스를 트레이스라고 하며$$,^{[1]: 7–8} 트레이스 이론으로 연구한다.

예

Given the alphabet ${\displaystyle \Sigma =\{a,b,c\}}$, a possible dependency relation is ${\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}}$, see picture.

해당 독립성은 $I{\displaystyle }$=${\displaystyle }${${\displaystyle }$( ${\displaystyle b}$, c${\displaystyle }$)${\displaystyle }$,${\displaystyle }$( c${\displaystyle }$, ${\displaystyle b}$)$}$ {\$displaystyle$ I$=\{(b,c),\(c$,b$)\backslash \}.$ 그러면 ${\displaystyle \mathrm{기호}}$ b${\displaystyle }$, c ${\displaystyle b,c}$는 서로$$ 독립적이며, $예{\displaystyle }$: ${\displaystyle a}$, ${\displaystystyle a,b}$은 종속적이다$$. ${\displaystyle \mathrm{문자열}}$ $a{\displaystyle }$ b ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle acba}$은(는) ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a}$ b ${\displaystyle a}$ ${\displaystyle abba}$ 및 ${\displaystyle b}$ b ${\displaystyle c}$ a b c ${\displaystyle a}$ ${\displaysty abbca}$과$($는) 동일하지만$$ 다른 문자열에는 해당되지 않는다.

참조