Ternary decision diagrams. Survey

摘要

This paper surveys seven types of TDDs: General-TDD, SOP-TDD, ESOP-TDD, AND-TDD, prime-TDD, EXOR-TDD, and Kleene-TDD. We give new definitions for SOP-TDDs and ESOP-TDDs and introduce unifying terminology. After showing some theorems on complexities, we compare the sizes of these TDDs using benchmark functions. Finally, we review important works on TDDs.