transitive closure


Also found in: Acronyms, Wikipedia.

transitive closure

The transitive closure R* of a relation R is defined by

x R y => x R* y x R y and y R* z => x R* z

I.e. elements are related by R* if they are related by R directly or through some sequence of intermediate related elements.

E.g. in graph theory, if R is the relation on nodes "has an edge leading to" then the transitive closure of R is the relation "has a path of zero or more edges to". See also Reflexive transitive closure.
References in periodicals archive ?
The archetypal example of a relation that cannot be expressed in first-order logic is the transitive closure of the edges in a graph.
For example, transitive closure of a relation R may be defined as follows [9]:
Since S is a directed tree labeled by a partition of V, its transitive closure is a preposet on V.
0] is the equality relation, the transitive closure of [[rho].
Notice that the use of a transitive closure step is not limited to the multi-pass approach [MMT+, 03].
Thus, the covered knowledge of a class c is the transitive closure of the relations subclass of class c and image of class c via a certain mapping.
Efficient Algorithms for the Instantiated Transitive Closure Queries, IEEE Transactions on Software Engineering, 17 (3).
The transitive closure of a directed graph G = (V, E) is the directed graph G* = (V, [E.
Given a generator set G it is obvious that its reflexive transitive closure, G*, will obey reflexivity and transitivity.
Only compute-closure is slightly more involved as it constructs a transitive closure.
If a structure is too complex to be viewed as a whole, the calculation tools can help calculate views (such as lifting, Hasse, transitive closure, and subsetting) and perform further analysis.
Section [4] is devoted to the formal definition of the new upper bound F and the trick concerning the transitive closure of the relation [[tau].