On the use of OBDDs in model-based diagnosis: An approach based on the partition of the model

In this paper, we discuss how Ordered Binary Decision Diagrams (OBDDs) can be exploited for the computation of consistency-based diagnoses in model-based diagnosis. Since it is not always possible to efficiently encode the whole system model within a single OBDD, we propose to build a set of OBDDs, each one encoding a portion of the original model. For each portion of the model, we compute an OBDD encoding the set of local diagnoses; the OBDD encoding global diagnoses is then obtained by merging all the local-diagnoses OBDDs. Finally, minimal-cardinality diagnoses can be efficiently computed and extracted.The paper reports formal results about soundness, completeness and computational complexity of the proposed algorithm. Thanks to the fact that encoding diagnoses is in general much simpler than encoding the whole system model, this approach allows for the successful computation of global diagnoses even if the system model could not be compiled into a single OBDD. This is exemplified referring to a challenging combinatorial digital circuit taken from the ISCAS85 benchmark.     

Exact OBDD Bounds for Some Fundamental Functions

Ordered binary decision diagrams (OBDDs) are nowadays one of the most common dynamic data structures or representation types for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Although many exponential lower bounds on the OBDD size of Boolean functions are known, there are only few functions where the OBDD size is asymptotically known exactly. In this paper the exact OBDD sizes of the fundamental functions multiplexer and addition of n-bit numbers are determined.     

On the Minimization of (Complete) Ordered Binary Decision Diagrams

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions. Some applications work with a restricted variant called complete OBDDs which is strongly related to nonuniform deterministic finite automata. One of its complexity measures is the width which has been investigated in several areas in computer science like machine learning, property testing, and the design and analysis of implicit graph algorithms. For a given function the size and the width of a (complete) OBDD is very sensitive to the choice of the variable ordering but the computation of an optimal variable ordering for the OBDD size is known to be NP-hard. Since optimal variable orderings with respect to the OBDD size are not necessarily optimal for the complete model or the OBDD width and hardly anything about the relation between optimal variable orderings with respect to the size and the width is known, this relationship is investigated. Here, using a new reduction idea it is shown that the size minimization problem for complete OBDDs and the width minimization problem are NP-hard.     

The Nonapproximability of OBDD Minimization

The size of ordered binary decision diagrams (OBDDs) is determined by the chosen variable ordering. A poor choice may cause an OBDD to be too large to fit into the available memory. The decision variant of the variable ordering problem is known to be NP-complete. We strengthen this result by showing that, unless P=NP, for each constant c>1 there is no polynomial time approximation algorithm with the performance ratio c for the variable ordering problem, i.e., no polynomial time algorithm that guarantees the computation of a variable ordering so that the resulting OBDD size is larger than the minimum size by a factor of at most c. This result justifies, also from a theoretical point of view, the use of heuristics for the variable ordering problem.     

Lower bounds on the OBDD size of two fundamental functions' graphs

Ordered Binary Decision Diagrams (OBDDs) are a data structure for Boolean functions which supports many useful operations. Among others it finds applications in CAD, model checking, and symbolic graph algorithms. Nevertheless, many simple functions are known to have exponential OBDD size with respect to their number of variables. In order to investigate the limits of symbolic graph algorithms which work on OBDD-represented graph instances, it is useful to have simply-structured graphs whose OBDD representation has exponential size. Therefore, we consider two fundamental functions with exponential lower bounds on their OBDD size and transfer these results to their corresponding graphs. Concretely, we consider the Indirect Storage Access function and the Hidden Weighted Bit function.     

Translation among CNFs, characteristic models and ordered binary decision diagrams

We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their Horn CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results hold on any class of functions having a basis of polynomial size.     

On the Incompressibility of Monotone DNFs

We prove optimal lower bounds for multilinear circuits and for monotone circuits with bounded depth. These lower bounds state that, in order to compute certain functions, these circuits need exactly as many OR gates as the respective DNFs. The proofs exploit a property of the functions that is based solely on prime implicant structure. Due to this feature, the lower bounds proved also hold for approximations of the considered functions that are similar to slice functions. Known lower bound arguments cannot handle these kinds of approximations. In order to show limitations of our approach, we prove that cliques of size n - 1 can be detected in a graph with n vertices by monotone formulas with O(log n) OR gates. Our lower bound for multilinear circuits improves a lower bound due to Borodin, Razborov and Smolensky for nondeterministic read-once branching programs computing the clique function.     

An efficient query learning algorithm for ordered binary decision diagrams

In this paper, we propose a new algorithm that exactly learns ordered binary decision diagrams (OBDDs) with a given variable ordering via equivalence and membership queries. Our algorithm uses at most n equivalence queries and at most 2n (log₂ m + 3n) membership queries, where n is the number of nodes in the target-reduced OBDD and m is the number of variables. The upper bound on the number of membership queries is smaller by a factor of O(m) compared with that for the previous best known algorithm proposed by [R. Gavaldà, D. Guijarro, Learning Ordered Binary Decision Diagrams, Proceedings of the 6th International Workshop on Algorithmic Learning Theory, 1995, pp. 228–238].     

Zero-suppressed BDDs and their applications

In many real-life problems, we are often faced with manipulating sets of combinations. In this article, we study a special type of ordered binary decision diagram (OBDD), called zero-suppressed BDDs (ZBDDs). This data structure represents sets of combinations more efficiently than using original OBDDs. We discuss the basic data structures and algorithms for manipulating ZBDDs in contrast with the original OBDDs. We also present some practical applications of ZBDDs, such as solving combinatorial problems with unate cube set algebra, logic synthesis methods, Petri net processing, etc. We show that a ZBDD is a useful option in OBDD techniques, suitable for a part of the practical applications. Published online: 15 May 2001     

A note on the size of OBDDs for the graph of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are the most common dynamic data structure for Boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. Analyzing the limits of symbolic graph algorithms for the all-pairs-shortest paths problem which work on OBDD-represented graph instances the so-called graph of integer multiplication has been investigated by Sawitzki [D. Sawitzki, Lower bounds on the OBDD size of graphs of some popular functions, in: Proc. of SOFSEM, LNCS, vol. 3381, 2005, pp. 298-309]. Using simple arguments his lower bound of ²n/768−1 on the size of OBDDs representing the graph of integer multiplication is improved up to ²n/24.     

一种基于熵的OBDD变量排序算法

有序二叉决策图（OBDD）是一种有效表示布尔函数的数据结构，其大小依赖于所采用的变量序。熵是定量描述布尔函数中变量重要性的一种方法。基于变量的熵值分析了高质量变量序的特征，给出了一种基于熵的OBDD变量排序算法。实验结果表明：该算法与模拟退火算法和遗传算法结果相当。时间仅为相应算法的80．84％和29．79％。     

On the size of (generalized) OBDDs for threshold functions

Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Among the many areas of application are hardware verification, model checking, and symbolic graph algorithms. Threshold functions are the basic functions for discrete neural networks and are used as building blocks in the design of some symbolic graph algorithms. In this paper the first exponential lower bound on the size of a more general model than OBDDs and the first nontrivial asymptotically optimal bound on the OBDD size for a threshold function are presented.     

On the size of randomized OBDDs and read-once branching programs for k-stable functions

In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is described.?As an application of this technique, a generic lower bound on the size of randomized OBDDs with bounded error is established for a class of functions which has been studied in the literature on branching programs for a long time. These functions have been called “k-stable” by Jukna. It follows that several standard functions are not contained in the analog of the class BPP for OBDDs. Furthermore, exponential lower bounds on the size of randomized kOBDDs are presented.?It is well known that k-stable functions with large k are hard for deterministic read-once branching programs. This is no longer true in the randomized case. It is shown here that a certain k-stable function due to Jukna, Razborov, Savicky, and Wegener has randomized branching programs of polynomial size, even with zero error. It follows that for the analogs of these classes defined in terms of the size of read-once branching programs. Received: September 3, 1998.     

A Comparison of Free BDDs and Transformed BDDs

Ordered binary decision diagrams (OBDDs) introduced by Bryant (IEEE Trans. on Computers, Vol. 35, pp. 677–691, 1986) have found a lot of applications in verification and CAD. Their use is limited if the OBDD size of the considered functions is too large. Therefore, a variety of generalized BDD models has been presented, among them FBDDs (free BDDs) and TBDDs (transformed BDDs). Here the quite tight relations between these models are revealed and their advantages and disadvantages are discussed.     

Decomposition of graphs and monotone formula size of homogeneous functions

Summary We show that every graph on n nodes can be partitioned by a number of complete bipartite graphs with O(n ²/log n) nodes with no edge belonging to two of them. Since each partition corresponds directly to a monotone formula for the associated quadratic function we obtain an upper bound for the monotone formula size of quadratic functions. Our method extends to uniform hypergraphs with fixed range and thus to homogeneous functions with fixed length of prime implicants. Finally we give an example of a quadratic function where each monotone formula built from arbitrary partitions of the graph (double edges allowed) is not optimal. That means we disprove the single-level-conjecture for formulae.     

The symbolic OBDD scheme for generating mechanical assembly sequences

Assembly sequence planning is one of typical combinatorial optimization problems, where the size of parts involved is a significant and often prohibitive difficulty. The compact storage and efficient evaluation of feasible assembly sequences is one crucial concern. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate the Boolean functions efficiently, and appears to give improved results for large-scale combinatorial optimization problems. In this paper, assembly knowledge models of liaison graph and translation function are formulated by OBDDs, and OBDD-based representation of assembly sequences is proposed. A novel OBDD-based procedure was presented to generate all geometrically feasible assembly sequences from the OBDDs of liaison graph and translation relation. This procedure can be used conveniently on the computer and all the feasible sequences can be derived. The great advantage of OBDD-based scheme is that the storage space of OBDD-based representation of feasible assembly sequences does not increase with the part count of assembly dramatically so quickly as that of AND/OR graph does. We developed the prototype tool for generating assembly sequence using Visual C++ and CUDD package, and undertake some experimental tests. It was shown that the OBDD scheme generated feasible assembly sequences correctly and completely.     

On the influence of the variable ordering for algorithmic learning using OBDDs

OBDDs with a fixed variable ordering are used successfully as data structure in experiments with learning heuristics based on examples. In this paper, it is shown that, for some functions, it is necessary to develop an algorithm to learn also a good OBDD variable ordering. There are functions with the following properties. They have OBDDs of linear size for optimal variable orderings. But for all but a small fraction of all variable orderings one needs large size to represent a list of randomly chosen examples. These properties are shown for simple functions like the multiplexer and the inner product.     

The Power of Nondeterminism and Randomness for Oblivious Branching Programs

Abstract. This paper abstracts and generalizes the known approaches for proving lower bounds on the size of various variants of oblivious branching programs (oblivious BPs for short), providing an easy-to-use technique which works for all nondeterministic and randomized modes of acceptance. The technique is applied to obtain the following results concerning the power of nondeterminism and randomness for oblivious BPs: <p>— Oblivious read-once BPs, better known as OBDDs (ordered binary decision diagrams), are used in many applications and their structure is well understood in the deterministic case. It has been open so far to compare the power of nondeterministic OBDDs with so-called partitioned BDDs which are a variant of nondeterministic branching programs also used in practice. A k -partitioned BDD has a nondeterministic node at the top by which one out of k deterministic OBDDs with possibly different variable orders is chosen. It is proven here that the two models are incomparable as long as k is bounded by a logarithmic function in the input length. <p>— It is shown that deterministic oblivious read-k -times BPs for an explicitly defined function require superpolynomial size, for k logarithmic in the input length, while there are Las Vegas oblivious read-twice BPs of linear size for this function. This is in contrast to the situation for OBDDs, for which the respective size measures are polynomially related. <p>— Furthermore, an explicitly defined function is presented for which randomized oblivious read-k -times BPs with bounded error require exponential size, while the function as well as its complement can be represented in polynomial size by nondeterministic oblivious read-k -times BPs and deterministic oblivious read-(k+1) -times BPs, where k=o(log n) .     

基于OBDD的编码算法

论文提出一个新的无损图像压缩算法,主要是通过有序二叉决策图(OBDD)的方法,寻找图像中重复的模式来减少其存储空间的一种变换编码,因而成为表示图像的另一种数据结构。我们通过该算法来寻找OBDD以精确地表示图像,并给出了其OBDD的有效编码,所获得的结果表明,所提出的算法及其编码是实现无损图像压缩的一种有效的方法。     

Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams

Ordered binary decision diagrams (OBDDs) have found many applications in the verification of combinational and sequential circuits, protocols, and the synthesis and analysis of systems. The applications are limited, since the expressive power of polynomial-size OBDDs is too restricted. Therefore, several more general BDD models are used. Partitioned OBDDs are OBDD models allowing restricted use of nondeterminism and different variable orderings. They are restricted enough such that the essential operations can be performed efficiently and they allow polynomial-size representations for many more functions than OBDDs. Here the expressive power of polynomial-size partitioned OBDDs is investigated. A tight hierarchy with respect to the number of parts in the partition is proved and partitioned OBDDs are compared with other BDD models. Received April 1998, and in final form September 1998.