transitive closure

Show Summary Details

Quick Reference

Of a transitive binary relation R. A relation R✻ defined as follows: x Ry iff there exists a sequence x=x0,x1,…, xn=y such that n > 0 and xiR xi+1, i=0,1,2,…, n-1 It follows from the transitivity property that if x R y then x Ry and that R is a subset of R✻.

x Ry

x=x0,x1,…, xn=y

xiR xi+1, i=0,1,2,…, n-1

if x R y then x Ry

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.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.