RelMDD-A Library for Manipulating Relations Based on MDDs
Abstract
Relation algebras is one of the state-of-the-art means used by mathematicians and computer
scientists for solving very complex problems. As a result, a computer algebra system for
relation algebras called RelView has been developed at Kiel University. RelView works
within the standard model of relation algebras. On the other hand, relation algebras do
have other models which may have different properties.
For example, in the standard model we always have L;L=L (the composition of two
(heterogeneous) universal relations yields a universal relation). This is not true in some
non-standard models. Therefore, any example in RelView will always satisfy this property
even though it is not true in general. On the other hand, it has been shown that every
relation algebra with relational sums and subobjects can be seen as matrix algebra similar
to the correspondence of binary relations between sets and Boolean matrices.
The aim of my research is to develop a new system that works with both standard
and non-standard models for arbitrary relations using multiple-valued decision diagrams
(MDDs). This system will implement relations as matrix algebras. The proposed structure
is a library written in C which can be imported by other languages such as Java or Haskell.