Transitive Closure

In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal (Lidl and Pilz 1998:337). If the binary relation itself is transitive, then the transitive closure is that same binary relation; otherwise, the transitive closure is a different relation. For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y", then the transitive closure of R on X is the relation R+: "it is possible to fly from x to y in one or more flights."

Read more about Transitive ClosureTransitive Relations and Examples, Existence and Description, Properties, In Graph Theory, In Logic and Computational Complexity, In Database Query Languages, Algorithms

Other articles related to "transitive closure, transitive":

Transitive Closure - Algorithms
... Efficient algorithms for computing the transitive closure of a graph can be found in Nuutila (1995) ... research went into efficient ways of computing transitive closure on distributed systems based on the MapReduce paradigm (Afrati et al ...
Hereditary Property - In Set Theory
... Equivalently, a set is hereditarily finite if and only if its transitive closure is finite ... set is hereditarily countable if and only if its transitive closure is countable ... A set x is said to have hereditarily the property if x itself and all members of its transitive closure satisfy, i.e ...
Transitive Set - Transitive Closure
... The transitive closure of a set X is the smallest (with respect to inclusion) transitive set which contains X ... Suppose one is given a set X, then the transitive closure of X is Note that this is the set of all of the objects related to X by the transitive closure ...
Pebble Automaton - Automata and Logic
... Let denote the set of tree properties describable in transitive closure first-order logic, and the same for positive transitive closure logic, i.e ... a logic where the transitive closure operator is not used under the scope of negation ... - the languages recognized by pebble automata are exactly those expressible in positive transitive closure logic ...
Reduction Systems - Abstract Rewriting Systems
... is the transitive closure of, where = is the identity relation, i.e ... is the smallest preorder (reflexive and transitive relation) containing ... It is also called the reflexive transitive closure of ...