HEURISTIC MINIMIZATION OF MULTIPLE-VALUED RELATIONS

A multiple-valued relation is a relation between inputs and outputs in which the input variables can assume more than two discrete values. M ultiple-valued relations arise quite naturally in many contexts. Using characteristic functions to represent relations, we can handle the pr oblem of minimizing multiple-valued relations as a generalization of t he conventional minimization problem of regular logic functions. Our a pproach is based on a state-of-the-art paradigm for the two level mini mization of functions. We clarify some special properties of relations , in contrast to functions, which must be carefully considered in real izing a high quality procedure for solving the minimization problem. A n efficient heuristic method to find an optimal sum-of-products repres entation for a multiple-valued relation is proposed and implemented in the program GYOCRO. It uses multiple-valued decision diagrams (MDD's) to represent the characteristic functions for the relations. Experime ntal results are presented and compared with previous exact and heuris tic Boolean relation minimizers to demonstrate the effectiveness of th e proposed method.