A Synthesis of Sub-Optimal Decision Programs

Abstract

Two heuristic techniques of suboptimal synthesis of decision diagrams (DDs) have been developed which are applicable to generally partial logic functions. The first technique generates ordered minimum or near-minimum size of DDs for M-valued logic functions, the second one sometimes yields more efficient DDs without a fixed ordering of binary variables. Both kinds of DDs are being used in designing and verification of digital systems where the minimum diagram size transforms directly into the minimum cost of function implementation or testing.