Learn R Programming

agop (version 0.2.4)

rel_is_transitive: Transitive Binary Relations

Description

A binary relation \(R\) is transitive, iff for all \(x\), \(y\), \(z\) we have \(xRy\) and \(yRz\) \(\Longrightarrow\) \(xRz\).

Usage

rel_is_transitive(R)

rel_closure_transitive(R)

rel_reduction_transitive(R)

Value

The rel_closure_transitive and rel_reduction_transitive functions return a logical square matrix. dimnames

of R are preserved.

On the other hand, rel_is_transitive returns a single logical value.

Arguments

R

an object coercible to a 0-1 (logical) square matrix, representing a binary relation on a finite set.

Details

rel_is_transitive finds out if a given binary relation is transitive. The algorithm has \(O(n^3)\) time complexity, pessimistically, where \(n\) is the number of rows in R. If R contains missing values behind the diagonal, the result will be NA.

The transitive closure of a binary relation \(R\), determined by rel_closure_transitive, is the minimal superset of \(R\) such that it is transitive. Here we use the well-known Warshall algorithm (1962), which runs in \(O(n^3)\) time.

The transitive reduction, see (Aho et al. 1972), of an acyclic binary relation \(R\), determined by rel_reduction_transitive, is a minimal unique subset \(R'\) of \(R\), such that the transitive closures of \(R\) and \(R'\) are equal. The implemented algorithm runs in \(O(n^3)\) time. Note that a transitive reduction of a reflexive relation is also reflexive. Moreover, some kind of transitive reduction (not necessarily minimal) is also determined in rel_reduction_hasse -- it is useful for drawing Hasse diagrams.

References

Aho A.V., Garey M.R., Ullman J.D., The Transitive Reduction of a Directed Graph, SIAM Journal on Computing 1(2), 1972, pp. 131-137.

Warshall S., A theorem on Boolean matrices, Journal of the ACM 9(1), 1962, pp. 11-12.

See Also

Other binary_relations: check_comonotonicity(), pord_nd(), pord_spread(), pord_weakdom(), rel_graph(), rel_is_antisymmetric(), rel_is_asymmetric(), rel_is_cyclic(), rel_is_irreflexive(), rel_is_reflexive(), rel_is_symmetric(), rel_is_total(), rel_reduction_hasse()