Dependency relation

Not to be confused with Dependence relation, which is a generalization of the concept of linear dependence among members of a vector space.

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

* If [math]\displaystyle{ (a,b)\in D }[/math] then [math]\displaystyle{ (b,a) \in D }[/math] (symmetric)
* If [math]\displaystyle{ a \in \Sigma }[/math], then [math]\displaystyle{ (a,a) \in D }[/math] (reflexive)

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

[math]\displaystyle{ \Sigma }[/math] is also called the alphabet on which [math]\displaystyle{ D }[/math] is defined. The independency induced by [math]\displaystyle{ D }[/math] is the binary relation [math]\displaystyle{ I }[/math]

[math]\displaystyle{ I = (\Sigma \times \Sigma) \setminus D }[/math]

That is, the independency is the set of all ordered pairs that are not in [math]\displaystyle{ D }[/math]. The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation [math]\displaystyle{ I }[/math] on a finite alphabet, the relation

[math]\displaystyle{ D = (\Sigma \times \Sigma) \setminus I }[/math]

is a dependency relation.

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

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

## Examples

200px|right Given the alphabet [math]\displaystyle{ \Sigma=\\{a,b,c\\} }[/math], a possible dependency relation is [math]\displaystyle{ D = \\{ (a,b),\, (b,a),\, (a,c),\, (c,a),\, (a,a),\, (b,b),\, (c,c) \\} }[/math], see picture.

The corresponding independency is [math]\displaystyle{ I=\\{(b,c),\,(c,b)\\} }[/math]. Then e.g. the symbols [math]\displaystyle{ b,c }[/math] are independent of one another, and e.g. [math]\displaystyle{ a,b }[/math] are dependent. The string [math]\displaystyle{ a c b b a }[/math] is equivalent to [math]\displaystyle{ a b c b a }[/math] and to [math]\displaystyle{ a b b c a }[/math], but to no other string.

## References

1. ↑ 1.0 1.1 1.2 1.3 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". in Rozenberg, G.; Diekert, V.. The Book of Traces. Singapore: World Scientific. ISBN 981-02-2058-8. http://www.cas.mcmaster.ca/~cas724/2007/paper2.pdf. Retrieved 18 April 2021.

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Dependency_relation&oldid=3366759"