transitive closure
transitive closure of a transitive binary relation R. A relation R* defined as follows: x R* y
iff there exists a sequence x = x0,x1,…, xn = y
such that n > 0 and xi R xi+1, i = 0,1,2,…, n–1
It follows from the transitivity property that if x R y then x R* y
and that R is a subset of R*.
Reflexive closure is similar to transitive closure but includes the possibility that n = 0. Transitive and reflexive closures play important roles in parsing and compiling techniques and in finding paths in graphs.
iff there exists a sequence x = x0,x1,…, xn = y
such that n > 0 and xi R xi+1, i = 0,1,2,…, n–1
It follows from the transitivity property that if x R y then x R* y
and that R is a subset of R*.
Reflexive closure is similar to transitive closure but includes the possibility that n = 0. Transitive and reflexive closures play important roles in parsing and compiling techniques and in finding paths in graphs.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
transitive closure