Dependency relation

Dependency relation

In mathematics and computer science, a dependency relation is a binary relation that is finite, symmetric, and reflexive; 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 is an element of the set on which the relation is defined, 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.

Let Σ denote the alphabet of all the letters of D. Then the independency induced by D is the binary relation I

I = \Sigma \times \Sigma - D

That is, the independency is the set of all ordered pairs that are not in D. Clearly, the independency is symmetric and irreflexive.

The pairs (Σ,D) and (Σ,I), or the triple (Σ,D,I) (with I induced by D) are sometimes called the concurrent alphabet or the reliance alphabet.

The pairs of letters in an independency relation induce an equivalence relation on the free monoid of all possible strings of finite length. The elements of the equivalence classes induced by the independency are called traces, and are studied in trace theory.

Examples

Consider the alphabet Σ = {a,b,c}. A possible dependency relation is

\begin{matrix} D 
 &=& \{a,b\}\times\{a,b\} \quad \cup \quad \{a,c\}\times\{a,c\} \\
 &=& \{a,b\}^2 \cup \{a,c\}^2 \\
 &=& \{ (a,b),(b,a),(a,c),(c,a),(a,a),(b,b),(c,c)\} 
\end{matrix}

The corresponding independency is

I_D=\{(b,c)\,,\,(c,b)\}

Therefore, the letters b,c commute, or are independent of one-another.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Dependency — or dependent may refer to: Contents 1 Sciences 1.1 Computer science 1.2 Economics 1.3 Linguistics 1.4 …   Wikipedia

  • Dependency theory — International relations theory  • Idealism  Liberalism   …   Wikipedia

  • Dependency graph — In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order… …   Wikipedia

  • Binary relation — Relation (mathematics) redirects here. For a more general notion of relation, see Finitary relation. For a more combinatorial viewpoint, see Theory of relations. In mathematics, a binary relation on a set A is a collection of ordered pairs of… …   Wikipedia

  • Dependency grammar — Hybrid constituency/dependency tree from the Quranic Arabic Corpus Dependency grammar (DG) is a class of syntactic theories developed by Lucien Tesnière. It is distinct from phrase structure grammars, as it lacks phrasal nodes. Structure is… …   Wikipedia

  • Relation — (Roget s Thesaurus) < N PARAG:Relation >N GRP: N 1 Sgm: N 1 relation relation bearing reference connection concern GRP: N 2 Sgm: N 2 cognation cognation Sgm: N 2 correlation correlation &c. 12 Sgm …   English dictionary for students

  • dependency theory — A set of theories which maintained that the failure of Third World states to achieve adequate and sustainable levels of development resulted from their dependence on the advanced capitalist world. Dependency theories developed in opposition to… …   Dictionary of sociology

  • dependency — A territory distinct from the country in which the supreme sovereign power resides, but belonging rightfully to it, and subject to the laws and regulations which the sovereign may think proper to prescribe. Posadas v. National City Bank of N. Y …   Black's law dictionary

  • dependency — A territory distinct from the country in which the supreme sovereign power resides, but belonging rightfully to it, and subject to the laws and regulations which the sovereign may think proper to prescribe. Posadas v. National City Bank of N. Y …   Black's law dictionary

  • relation — n. 1. Recital, narration, narrative, account, statement, story, history, chronicle, tale, description, detail, report, rehearsal. 2. Connection, relationship, dependency, bearing. 3. Reference, respect, regard. 4. Connection, relative position. 5 …   New dictionary of synonyms

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”