Reduction of sizes of multi-valued decision diagrams by copy properties

Abstract

Copy Decision Diagrams (CDDs) are an approach to the reduction of sizes of Multi-Terminal Binary Decision Diagrams (MTBDDs) by using the copy properties of discrete functions. Functions having different types of copy properties can be efficiently represented by CDDs. Illustrative examples are Walsh and Reed-Muller functions as well as different binary codes. In this paper we consider an extension of this idea to Multi-valued Decision Diagrams (MDDs). We propose Copy MDDs (CMDD) as a modification of MDDs that exploits copy properties of functions besides properties already used in reduction of MDDs. Experimental results show reduction capabilities of CMDDs.