Translation

powered by

Computing (FOLDOC) dictionary

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.