Abstract

This tutorial paper discusses the known representations based on Binary
Decision Diagrams (BDDs) for various types of discrete objects:
incompletely specified functions, sets, finite state machines, binary and
multi-valued relations, etc. While presenting the known material, the
emphasis is on those aspects of implicit representations that are
important to achieve speed-up in computation.

The new material includes implicit representations for dichotomies,
partitions, set systems, and information measures. The last type of
objects, information measures, constitute a promising approach to problem
solving in a number of areas, including decomposition of discrete
functions and finite state machines.

Multi-valued relations (MVRs) are presented as the most general
representation for all the considered classes on discrete objects. Two
complementary ways of representing MVRs are proposed: binary-encoded
multi-valued decision diagrams (BEMDDs) and labeled rough partitions
(LRPs). The sizes of BEMDDs and LRPs are compared using a set of
multi-valued benchmarks.