Dependency relation information

In computer science, in particular in concurrency theory, a dependency relation is a binary relation on a finite domain $\Sigma$ ,^[1]^: 4 symmetric, and reflexive;^[1]^: 6 i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs $D$ , such that

If $(a,b)\in D$ then $(b,a)\in D$ (symmetric)
If $a\in \Sigma$ , then $(a,a)\in D$ (reflexive)

In general, dependency relations are not transitive; thus, they generalize the notion of an equivalence relation by discarding transitivity.

$\Sigma$ is also called the alphabet on which $D$ is defined. The independency induced by $D$ is the binary relation $I$

I=(\Sigma \times \Sigma )\setminus D

That is, the independency is the set of all ordered pairs that are not in $D$ . The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation $I$ on a finite alphabet, the relation

D=(\Sigma \times \Sigma )\setminus I

is a dependency relation.

The pair $(\Sigma ,D)$ is called the concurrent alphabet.^[2]^: 6 The pair $(\Sigma ,I)$ is called the independency alphabet or reliance alphabet, but this term may also refer to the triple $(\Sigma ,D,I)$ (with $I$ induced by $D$ ).^[3]^: 6 Elements $x,y\in \Sigma$ are called dependent if $xDy$ holds, and independent, else (i.e. if $xIy$ holds).^[1]^: 6

Given a reliance alphabet $(\Sigma ,D,I)$ , a symmetric and irreflexive relation $\doteq$ can be defined on the free monoid $\Sigma ^{*}$ of all possible strings of finite length by: $xaby\doteq xbay$ for all strings $x,y\in \Sigma ^{*}$ and all independent symbols $a,b\in I$ . The equivalence closure of $\doteq$ is denoted $\equiv$ or $\equiv _{(\Sigma ,D,I)}$ and called $(\Sigma ,D,I)$ -equivalence. Informally, $p\equiv q$ holds if the string $p$ can be transformed into $q$ by a finite sequence of swaps of adjacent independent symbols. The equivalence classes of $\equiv$ are called traces,^[1]^: 7–8 and are studied in trace theory.

^ ^a ^b ^c ^d IJsbrand Jan Aalbersberg and Grzegorz Rozenberg (Mar 1988). "Theory of traces". Theoretical Computer Science. 60 (1): 1–82. doi:10.1016/0304-3975(88)90051-5.
^ Vasconcelos, Vasco Thudichum (1992). Trace semantics for concurrent objects (MsC thesis). Keio University. CiteSeerX 10.1.1.47.7099.
^ Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). The Book of Traces. Singapore: World Scientific. ISBN 981-02-2058-8. Retrieved 18 April 2021.

[Aalbersberg.Rozenberg.1988-1] IJsbrand Jan Aalbersberg and Grzegorz Rozenberg (Mar 1988). "Theory of traces". Theoretical Computer Science. 60 (1): 1–82. doi:10.1016/0304-3975(88)90051-5.

[2] Vasconcelos, Vasco Thudichum (1992). Trace semantics for concurrent objects (MsC thesis). Keio University. CiteSeerX 10.1.1.47.7099.

[3] Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). The Book of Traces. Singapore: World Scientific. ISBN 981-02-2058-8. Retrieved 18 April 2021.

Dependency relation information

and 25 Related for: Dependency relation information

Dependency relation

Dependency

Dependency grammar

Phrase structure grammar

Functional dependency

Equivalence relation

Dependency graph

Multivalued dependency

Homogeneous relation

Media system dependency theory

Dependency theory

Transitive dependency

Phrase structure rules

Parse tree

Immediate constituent analysis

Sentence diagram

Third normal form

Circular dependency

Adpositional phrase

Syntax

Second normal form

Grammar

Binary relation

Relational model

Fourth normal form