We describe the Ordered Ternary Decision Diagram (OTDD) which can be directly evaluated even when given any number of undefined input logic values. Based on Kleenean strong ternary logic, the OTDD unifies the concepts of "unknown input" with "don't-care output" for incompletely-specified Boolean functions. The OTDD permits functions having nontrivial don't-care sets to be represented as single diagrams and to be directly processed against each other. We define the full OTDD and the abbreviated OTDD. We examine advantages of the OTDD over the commonly-used dual-OBDD method of representing incomplete functions, for LGSynth93 standard benchmarks. We outline a single package for computations with both shared, reduced OTDDs and OBDDs.
Index Terms:
ternary logic; symbol manipulation; Boolean functions; incompletely specified functions; correct evaluation; indeterminate input values; Ordered Ternary Decision Diagram; OTDD; symbolic computation
Citation:
G. Jennings, "Symbolic incompletely specified functions for correct evaluation in the presence of indeterminate input values," hicss, pp.23, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995