Titlebook: Representations of Discrete Functions; Tsutomu Sasao,Masahiro Fujita Book 1996 Kluwer Academic Publishers 1996 CAD.algorithms.complexity.c

figurine

碎石头

Multi-Terminal Binary Decision Diagrams and Hybrid Decision Diagrams,ow multi-terminal binary decision diagrams (MTBDDs) can be used to represent such functions concisely. The Walsh transform and Reed-Muller transform have numerous applications in computer-aided design, but the usefulness of these techniques in practice has been limited by the size of the binary valu

蛰伏

Edge Valued Binary Decision Diagrams,functions (PBF). .s are particularly useful when both arithmetic and Boolean operations are required. We describe a general algorithm on .s for performing any binary operation that is closed over the integers. Next, we discuss the relation between the probability expression of a Boolean function and

Arroyo

Arithmetic Transform of Boolean Functions,ns. Such arithmetic transformations can give us new insight into solving some interesting problems. For example, the transformed functions can be easily evaluated (simulated) on integers or real numbers. Through such arithmetic simulation we can probabilistically verify a pair of functions with much

侵蚀

,OKFDDs — Algorithms, Applications and Extensions,nctions. OKFDDs are a generalization of Ordered Binary Decision Diagrams and Ordered Functional Decision Diagrams and as such provide a more compact representation of the functions than either of the two decision diagrams. We review basic properties of OKFDDs and study methods for their efficient re

Synapse

数量

Radiculopathy

Satisfiability Problems for OFDDs,UNT. We prove that SAT-ALL has a running time linear in the product of the number of satisfying assignments and the size of the given OFDD. Counting the satisfying assignments in an OFDD is proved to be #.-complete, and thus not possible in polynomial time unless P=NP.

美食家

Complexity Theoretical Aspects of OFDDs,or to OBDDs (ordered binary decision diagrams). Most of the complexity theoretical problems have been solved for OBDDs. Here some results for OFDDs are proved. It is NP-complete to decide whether a function represented by some OFDD can be represented by an OFDD of size s using another variable order

切掉