ON PROPERTIES OF KLEENE TDDS

Three types of ternary decision diagrams considered: AND_TDDs, EXOR_TD Ds, and Kleene_TDDs. Kleene_TDDs are useful for logic simulation in th e presence of unknown inputs. Let N(BDD : f), N(AND_TDD : f), and N(EX OR_TDD : f) be the number of non-terminal nodes in the BDD, the AND_TD D. and the EXOR_TDD for f, respectively. Let N(Kleene_TDD : F) be the number of nan-terminal nodes in the Kleene_TDD for F, where F is the r egular ternary function corresponding to f. Then N(BDD : f) less than or equal to N(TDD : f). For parity functions, N(BDD : f) = N(AND_TDD : f) = N(EXOR_TDD : f) = N(Kleene_TDD : F). For unate functions, N(BDD : f) = N(AND_TDD : f). The sizes of Kleene_TDDs are O(3(n)/n), and O(n (3)) for arbitrary functions, and symmetric functions, respectively. T here exist a an-variable function, where Kleene_TDDs require O(n) node s with the best order, while O(3(n)) nodes in the worst order.