Závislostní vztah - Dependency relation - Wikipedia

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Závislostní vztah"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Březen 2008) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačová věda, zejména v teorie souběžnosti, a vztah závislosti je binární relace to je konečné,^[1]:4 symetrický, a reflexní;^[1]:6 tj. konečný vztah tolerance. To znamená, že se jedná o konečný soubor objednané páry ${ displaystyle D}$, takový, že

• Li ${ displaystyle (a, b) v D}$ pak ${ displaystyle (b, a) v D}$ (symetrický)
• Li ${ displaystyle a}$ je prvek množiny, na kterém je vztah definován ${ displaystyle (a, a) v D}$ (reflexivní)

Obecně platí, že závislostní vztahy nejsou tranzitivní; tak zobecňují pojem vztah ekvivalence vyřazením tranzitivity.

Li ${ displaystyle Sigma}$ (také zvaný abeceda ) označuje množinu, na které ${ displaystyle D}$ je definován, pak nezávislost vyvolané ${ displaystyle D}$ je binární relace ${ displaystyle I}$

${ displaystyle I = ( Sigma krát Sigma) setminus D}$

To znamená, že nezávislost je množina všech uspořádaných párů, které nejsou v ${ displaystyle D}$. Vztah nezávislosti je symetrický a nereflexivní. Naopak, vzhledem k jakémukoli symetrickému a nereflexivnímu vztahu ${ displaystyle I}$ na konečné abecedě vztah

${ displaystyle D = ( Sigma krát Sigma) setminus I}$

je vztah závislosti.

Tyto páry ${ displaystyle ( Sigma, D)}$ a ${ displaystyle ( Sigma, I)}$,^{[Citace je zapotřebí ]} nebo trojnásobek ${ displaystyle ( Sigma, D, I)}$ (s ${ displaystyle I}$ vyvolané ${ displaystyle D}$) se někdy nazývají souběžná abeceda^{[Citace je zapotřebí ]} nebo spoléhání abeceda. V tomto případě prvky ${ displaystyle x, y in Sigma}$ jsou nazývány závislý -li ${ displaystyle xDy}$ drží, a nezávislý, jinak (tj. pokud ${ displaystyle xIy}$ drží).^[1]:6

Vzhledem k abecedě spoléhání ${ displaystyle ( Sigma, D, I)}$, symetrický a irreflexivní vztah ${ displaystyle doteq}$ lze definovat na volný monoid ${ displaystyle Sigma ^ {*}}$ všech možných řetězců konečné délky: ${ displaystyle xaby doteq xbay}$ pro všechny struny ${ displaystyle x, y in Sigma ^ {*}}$ a všechny nezávislé symboly ${ displaystyle a, b v I}$. The uzavření rovnocennosti z ${ displaystyle doteq}$ je označen ${ displaystyle equiv}$nebo ${ displaystyle equiv _ {( Sigma, D, I)}}$a zavolal ${ displaystyle ( Sigma, D, I)}$-rovnocennost. Neformálně, ${ displaystyle p equiv q}$ platí, pokud řetězec ${ displaystyle p}$ lze přeměnit na ${ displaystyle q}$ konečnou posloupností swapů sousedních nezávislých symbolů. The třídy ekvivalence z ${ displaystyle equiv}$ jsou nazývány stopy,^[1]:7–8 a jsou studováni v teorie stop.

Příklady

Vzhledem k abecedě ${ displaystyle Sigma = {a, b, c }}$, možný vztah závislosti je ${ displaystyle D = {(a, b), , (b, a), , (a, c), , (c, a), , (a, a), , (b, b), , (c, c) }}$, viz obrázek.

Odpovídající nezávislost je ${ displaystyle I = {(b, c), , (c, b) }}$. Pak např. symboly ${ displaystyle b, c}$ jsou na sobě nezávislé a např. ${ displaystyle a, b}$ jsou závislí. Řetězec ${ displaystyle acbba}$ je ekvivalentní k ${ displaystyle abcba}$ a do ${ displaystyle abbca}$, ale k žádnému jinému řetězci.

Reference

Tento abstraktní algebra související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

Tento počítačová věda článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.