Normal forms for binary relations

We consider the representable equational theory of binary relations, in a language expressing composition, converse, and lattice operations. By working directly with a presentation of relation expressions as graphs we are able to define a notion of reduction which is confluent and strongly normalizing and induces a notion of computable normal form for terms. This notion of reduction thus leads to a computational interpretation of the representable theory.

Authors

• Daniel J. Dougherty
• Claudio Gutiérrez

Keywords

• Binary relations
• Graph representation
• Normal forms
• Omitting minors