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 ?
(i) The introduction of the concept of transitive closure according to a given property.
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]:
In the sequel, we prove that R is the transitive closure of R, which also implies that R is an equivalent relation on U.
Since S is a directed tree labeled by a partition of V, its transitive closure is a preposet on V.
(*) the transitive closure [[pi].sub.i] of [[rho].sub.i] is contained in [[rho].sub.i+1] and the relation [[rho].sub.i+1]/[[pi].sub.i] induced by [[rho].sub.i+1] on the set of equivalence classes Q/[[pi].sub.i] is a partial ordering.
Notice that the use of a transitive closure step is not limited to the multi-pass approach [MMT+, 03].
Fuzzy transitive-closure coherence axiom (FTCCA): for any S [member of] B and x [member of] X, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [bar.R] denotes the transitive closure of R.
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.sup.*]), which has an edge corresponding to every directed path in G.