Representations of Discrete Functions

1 Graph-Based Representations of Discrete Functions.- 1.1 Introduction.- 1.2 BDDs.- 1.3 Representation of Multi-Valued Functions.- 1.4 Representation of Cube Sets.- 1.5 Summary.- References.- 2 Representations of Logic Functions Using EXOR Operators.- 2.1 Introduction.- 2.2 Trees using EXOR Operators.- 2.3 Various AND-EXOR Expressions.- 2.4 Decision Diagrams using EXORs.- 2.5 EXOR Ternary Decision Diagrams.- 2.6 Conclusion and Comments.- References.- 3 Spectral Transform Decision Diagrams.- 3.1 Introduction.- 3.2 Matrix Theory.- 3.3 BDDs and FDDs.- 3.4 Generalization.- 3.5 Arithmetic Transform.- 3.6 Walsh Transform.- 3.7 Reduced STDDs.- 3.8 Relation Between STDDs and other DDs.- 3.9 STDDs for Arithmetic Functions.- 3.10 Conclusions and Comments.- References.- 4 Multi-Terminal Binary Decision Diagrams and Hybrid Decision Diagrams.- 4.1 Introduction.- 4.2 Multi-terminal Binary Decision Diagrams.- 4.3 Matrix Operations.- 4.4 Spectral Transformations of Binary Valued Functions.- 4.5 Kronecker Transformations.- 4.6 Hybrid Decision Diagrams.- 4.7 Summary and Directions for Future Research.- References.- 5 Edge Valued Binary Decision Diagrams.- 5.1 Introduction.- 5.2 Pseudo Boolean Functions.- 5.3 Edge Valued Binary Decision Diagrams.- 5.4 The Probability Transform and its Spectrum.- 5.5 Reed-Muller Coefficients.- 5.6 Factored Edge Valued Binary Decision Diagrams.- 5.7 Summary.- References.- 6 Arithmetic Transform of Boolean Functions.- 6.1 Arithmetic Transforms: Why they Need be Studied.- 6.2 An Integer-Valued Arithmetic Transform.- 6.3 More on A-Transforms: Introducing Numeric Values.- 6.4 Field Expressions and BDDs: Semi-Numeric Decision Diagrams.- 6.5 Application in Probabilistic Equivalence Verification.- 6.6 Conclusion.- References.- 7 OKFDDs — Algorithms, Applicationsand Extensions.- 7.1 Introduction.- 7.2 Ordered Kronecker Functional Decision Diagrams.- 7.3 Basic Algorithms on OKFDDs.- 7.4 Implementation of an OKFDD Package.- 7.5 Applications and Extensions.- 7.6 Conclusions.- References.- 8 Exact Minimization of FPRMS Using Multi-Terminal EXOR TDDs.- 8.1 Introduction.- 8.2 Definition and Basic Properties.- 8.3 Optimization of FPRMs.- 8.4 Data Structure and Implementation.- 8.5 Optimization of Kronecker Expressions.- 8.6 Experimental Results.- 8.7 Conclusion and Comments.- References.- 9 Multiple Domain Logic Synthesis.- 9.1 Introduction.- 9.2 Basics.- 9.3 The Multiple Domain Minimization Approach.- 9.4 Results.- 9.5 Conclusion.- References.- 10 Satisfiability Problems for OFDDs.- 10.1 Introduction.- 10.2 Fundamental Concepts and Definitions.- 10.3 Computing Satisfying Assignments.- 10.4 Counting Satisfying Assignments.- 10.5 Conclusions.- 10.6 Proof of Theorem 2.- References.- 11 Complexity Theoretical Aspects of OFDDs.- 11.1 Introduction.- 11.2 Improving the Variable Ordering of OFDDs is NP-complete.- 11.3 Minimal OFDD Covers.- 11.4 An Exponential Blow-Up by the Replacement of Variables by Constants.- 11.5 The Effect of Local Changes of the Variable Ordering.- 11.6 Conclusion.- References.- 12 Ternary Decision Diagrams and their Applications.- 12.1 Introduction.- 12.2 Definitions and Basic Properties.- 12.3 AND TDDs.- 12.4 Reduced Ordered TDD and SOP.- 12.5 Prime TDD and Generation of Prime Implicants.- 12.6 BDDs and TDDs for Symmetric Functions.- 12.7 Experimental Results.- 12.8 Conclusion and Comments.- References.- 13 Or-and-Or Three-Level Networks.- 13.1 Introduction.- 13.2 Upper Bound on the Number of Gates.- 13.3 Lower Bound on the Number of Gates.- 13.4 Experimental Results.- 13.5 Conclusion and Comments.- References.- Exercise.- Appendix A.- Appendix B.