数理解析研究所講究録
第 833 巻 1993 年 242-249

242

$NP$

-completeness of Minimum Binary Decision
Diagram Identification Problems

Yasuhiko TAKENAGA and Shuzo YAJIMA
武永康彦

矢島脩三

Faculty of Engineering, Kyoto University

1

Introduction

An Ordered Binary Decision Diagram (or simply BDD) $[1, 2]$ is a graph representation ofa Boolean function. The BDD representation of Boolean functions has the following good
properties : there exists a unique canonical form for any Boolean function, many of practical
Boolean functions are represented in feasible size, various basic operations such as reduction(minimization) and Boolean operations are executed efficiently.
Owing to the excellent properties, BDD’s have come to be indispensable in application
programs of logic design verification fault diagnosis of logic circuits, logic synthesis and so on.
In the applications, the use of BDD’s enabled us to deal with large scale circuits efficiently.
On the other hand, researches on the properties of BDD’s from theoretical aspects havecome to be made at last recently. [3] and [4] deal with the number of nodes necessary torepresent varioous Boolean functions. [3] proves that the function to represent the output of amultiplier cannot be represented within polynomial size. [5] and [6] define a class of languages
expressed by polynomial size BDD’s and discuss the relation to various complexity classes. [7]and [8] take up the efficiency of basic operations on BDD’s. They show that there are NC
algorithms for the operations.
In this paper, we consider the problems to identify the minimum BDD that satisfies given
positive examples and negative examples. Although the size of BDD’s may largely vary according to the variable ordering, we assume in this paper that the variable ordering is fixed.
The width and the number of nodes are used as the measure of minimality. We prove that, inboth cases, the minimum BDD identification problem is NP-complete. If we regard that thevalues for the assignments which are not in the examples to be undefined, this problem is tofind a simple completely specified Boolean function that is consistent with a given incompletely
specified function.
This problem is also closely related to computational learning theory. In the PAC(Probably
Approximately $Correct$ ) $- learning$ model $[9, 10]$ , the learner generates a hypothesis based on
the examples given by the teacher. It is known that k-term DNF, k-clause CNF, -formulas
RP [11]. In the same manner,
are not learnable under the PAC-learning model unless NP
we can observe from the above result that k-width BDD and k-size BDD are not learnable inpolynomial time under PAC-learning model unless NP $=RP$ .
$\mu$

$=$

243
Binary Decision Diagrams

2

An Ordered Binary Decision Diagram (BDD) $[1, 2]$ is a directed acyclic graph that representsa Boolean function. The nodes of a BDD consist of variable nodes and two value nodes. The
outdegree of a variable node is 2. The edges are called O-edge and l-edge. One of the variablenode is called a root node whose indegree is . Two value nodes are called O-node and l-node.
A BDD is represented by a root node and a set of 4-ples $(i, index(i),$ $low(i),$ $high(i))$ that
correspond to variable nodes, whereis a node number,index(i) $\in\{1,2, \cdots N\}$ ( $N$ is the number of variables) is an index of the variable that is
assigned to the node, andlow(i), high (i) are the numbers of the nodes pointed by the O-edge and the l-edge respectively. The node number of O-node is and that of l-node is 1.
The Boolean function that is represented by node , denoted by , is defined as follows by
Shannon’s expansion.
$f_{0}=0,$ $f_{1}=1$ ,
$0$

$i$

$0$

$i$

$f_{i}$$f_{i}=x_{index(i)}\cdot f_{high(i)}+\overline{x_{index(i)}}\cdot f_{low(i)}$When the root node of a BDD is , the function represented by is $f_{A}=f_{a}$ .
For a permutation on $\{1, 2, \cdots N\}$ , every node of a BDD satisfies
$A$

$A$

$a$

$\pi$

$\pi(index(i))<\pi(index(low(i)))$ ,$\pi(index(i))<\pi(index(high(i)))$ ,is called a variable ordering. $\pi(index(i))$ is
except when low(i) or high(i) is a value node.
denoted by level(i) and is called the level of node or the level of $x_{index(i)}$ .
When two nodes and represent the same function, they are called to be equivalent and.
denoted byifflevel(i) $=level(j)$ ,high $(i)\equiv high(j)$ ,low $(i)\equiv low(j)$ .
Node is called to be redundant whenhigh(i) $=low(i)$ .
A BDD is called a dense BDD when all the variable nodes satisfy
level $(i)+1=level(low(i))=level(high(i))$ .
Any BDD can be transformed to a dense BDD by adding redundant nodes.
A dense BDD which has no equivalent nodes is called a quasi-reduced BDD [12]. A BDD
which has no equivalent nodes and no redundant nodes is called a reduced BDD.
Let width $(k)$ be the sum of the number of nodes in level and the number of edges thatpasses through level . The width of a BDD is defined by $\max_{1\leq k\leq n}width(k)$ .
BDD’s defined above have following good properties.
$\pi$

$i$

$i$

$i\equiv j$$j$$i\equiv j$

$i$

$k$

$k$

$\bullet$A Boolean function is uniquely represented by a reduced BDD or a quasi-reduced BDD,
provided that the variable ordering is fixed. Therefore, the equivalence of Boolean functions is easily checked.

244$\bullet$

For n-variable Boolean functions, the number of nodes is $O(2^{n}/n)$ , however, many practical Boolean functions are compactly represented.

3

Minimum Binary Decision Diagram Identification

3.1

NP-completeness of Minimum Binary Decision Diagram Identffication Problems

In this section, we consider the complexity of identifying minimum BDD’s from positive examples and negative examples. We assume in this paper that the variable ordering of a BDD
is fixed. As the measures of the size of BDD’s, we consider both the width and the number ofnodes.
Definition : MINIMUM WIDTH BDD IDENTIFICATION
Input : A set $EX$ of examples and a positive integer .
Output : Is there a BDD of width less than or equal to that satisfies all the examples?
Definition : MINIMUM BDD IDENTIFICATION
Input : A set $EX$ of examples and a positive integer .
Output : Is there a BDD which has less than or equal to nodes that satisfies all the examples?
Note that an example is a pair \langle $f(x)$ }, where $x\in\{0,1\}^{n}$ is an assignment for variables, and $f(x)\in\{0,1\}$ is the value of for the assignment. The variable ordering of
the BDD is fixed as $\pi(x_{i})=i,$ $1\leq i\leq n$ .
, a function that satisfies $EX$ is considered as
When we assign values to$(n-k)$ -variable incompletely specified Boolean function. Let $f,g,$ be incompletely specified
when $g(x)=1$ if $f(x)=1$ and $g(x)=0if.f(x)=0$ for
Boolean functions. We denote. Let $H=\{h|f\subseteq h, g\subseteq h\}$ ,all . and can be unified iff there exists s.t.
.
then $h’=u\{f,g\}$ is defined as $h’\in H,$
Theorem 1 MINIMUM WIDTH BDD IDENTIFICATION is NP-complete.
Proof First, we show a nondeterministic polynomial time algorithm for MINIMUM WIDTHBDD IDENTIFICATION.
Let $prefix_{i}(x)$ denote the $i(0\leq i\leq n)$ highest bits of .
[Algorithm MinIdent]
$k$

$k$

$k$

$k$

$x,$

$x_{1},$ $x_{2},$$f$$\cdots,$ $x_{n}$$x_{1},$ $x_{2},$$\cdots,$ $x_{n}$$h$$f\subseteq g$

$x$

$f$

$h$

$g$

$f\subseteq h,$$g\subseteq h$$\forall h\in Hh\subseteq h’$$x$

1 : $P=\{prefix_{i}(x)|\{x, f(x)\rangle\in EX, 1\leq i\leq n\}$ . For all $y\in P,$ $1\leq|y|<n$ , guess$g(y) \in\{1,2, --, \min(k, 2^{|y|})\}$ . For $y\in P$ s.t. $|y|=n$ , let $g(y)=f(y)$ .

2 : For $1\leq i\leq n,$ $1\leq j\leq k$ , let $P_{i,j}=\{pre.fix_{i}(x)|g(prefix_{i}(x))=j\}$ .
, check whether the following conditions are satisfied. 1)$g(r\cdot 0)=g(s\cdot 0)$ for all
s.t. $s\in P_{i,j},$ $r\cdot 0\in P$ and $s\cdot 0\in P,$ ) $g(r\cdot 1)=g(s\cdot 1)$
s.t. $s\in P_{i,j},$ $r\cdot 1\in P$ and $s\cdot 1\in P$ .
for all

3: For $1\leq i\leq n,$$1\leq j\leq k$
$r,$

$r,$

$s$

$s$

$2$

$r,$

$r,$

If the conditions are satisfied for all $i,j,$
or equal to .
$k$

$r,$

$s$

, then there exists a BDD of width less than

245
We can see that $|P|\leq|EX|\cross n$ and $|P_{i,j}|\leq|EX|$ . Therefore the time requirement of
Algorithm MinIdent is bounded by a polynomial of and $|EX|$ .
We shall claim the correctness of Algorithm MinIdent. We can construct a BDD as follows.
The path corresponding to an assignment is on the $g(prefix_{i-1}(x))$ -th node in level . For
each $1\leq i\leq n,$ $r\in P(|r|=i-1)$ , the O-edge from the $f(r)$ -th node of level points $f(r\cdot 0)$ -th
node of level $i+1$ if $r\cdot 0\in P$ , and the l-edge points $f(r\cdot 1)$ -th node if $r\cdot 1\in P$ .
If the conditions of 3: are not satisfied, there exists a node that has more than one O-edges
or l-edges. Otherwise, each node has at most one O-edge and l-edge, and the generated graphis a subgraph of a k-width BDD. Moreover, we can easily see that there are paths from theroot node to constant nodes for all the assignments given as examples. The edges which are
not generated by the above method may point any node.
Next, we show the NP-hardness of MINIMUM WIDTH BDD IDENTIFICATION by the
reduction from GRAPH K-COLORABILITY.
Definition : GRAPH K-COLORABILITY
Input : An undirected graph $G(V, E)$ and a positive integer .
Output : Is there a function : $Varrow\{1,2, -- , k\}$ s.t. $f(i)\neq f(j)$ for all the edges $(i,j)\in E$ ?
Let $N$ denote the number of nodes in . We can assume without loss of generality that $N$
is a power of 2.
The Boolean function of the reduced problem has $6logN+2$ variables. The set of examples
are as follows :$\{B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot 00\cdot B_{r}\cdot B_{s}, f_{i}(r, s)\}(r<s)$ ,
$n$

$i$

$x$

$i$

$k$

$f$

$G$

$\{B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot 01\cdot B_{r}\cdot B_{s},$$f_{j}(r, s)\rangle$$\langle B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot 10\cdot B_{r}\cdot B_{s},$$f_{p}(r, s)${{$(r<s)$ ,} $(r<s)$ ,$B_{N-1}\cdot B_{N-1}\cdot B_{N-1}\cdot B_{q}\cdot 11\cdot B_{r}\cdot B_{s},$$g_{q}(r, s)\rangle$$(r<s, (r, s)\in E)$ and( $r<s$ , excepting $i=j=p=N-1$ ),$s\leq N-1$ andwhere $0\leq i,j,p,$
is a binary representation of an integer .
$\cdots,g_{N-1}$ are defined as follows :and$f_{t}(B_{t}, B_{s})=0$ iff $t<s$ ,$f_{t}(B_{r}, B_{t})=1$ iff $r<t$ ,$g_{t}(B_{t}, B_{s})=0$ iff $t<s$ and $(t, s)\in E$ and$B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot 11\cdot B_{r}\cdot B_{s},$$q,$ $r,$$f_{q}(r, s)\rangle$$i$$B_{i}$$f_{0},$ $f_{1},$$\cdots,$$f_{N-1}$$g_{0},g_{1},$iff $r<t$ and $(r, t)\in E$ .
The positive integer to bound the width of the BDD is $N^{4}-N+k$ .
The number of examples is$(N-1)(4N^{4}-N)+2|E|=O(N^{5})$ .
The examples can be generated using $O(logn)$ space.
We shall prove that there exists a $(N^{4}-N+k)$ -width BDD that satisfy all the examples
iff graphis k-colorable. In order to count the width of each level. we use the following
propositions.
Propositions 1. For any $i.j(i\neq j, 0\leq i\leq N-1)$ . andcannot be unified.
$(i.j)\not\inE$$g_{j}(i\neqj)$2.
can be unified iff.
and$g_{i}\subseteq
f_{i}(0\leq
i\leq
N-1)$
.
3.
4. If
can be unified, $g’=u\{g;_{1},g_{i_{2}}. \cdots g_{i_{m}}\}$ can be unified with any of$f_{i_{J}}(0\leq j\leq m)$ .
$g_{t}(B_{r}, B_{t})=1$$G$$f_{i}$$g_{i}$$g_{i_{1}},g_{i_{2}},$$\cdots g_{i_{m}}$$f_{j}$

246
Proof 1. When $i<j,$ $f_{i}(i,j)=0,$ $f_{j}(i.j)=1$ .
and $f_{j}(i<j)$ differ only when the
4. We have only to prove the case where $m=2$ .
can be unified, because $(i,j)\not\in E$ , that is, $g_{i}(i,j)$parameters are and . However, andand $g_{j}(i,j)$ are undefined. Therefore, and $gj$ ( and ) can be unified.
The next lemma follows from Proposition 2.
Lemma 1 $g_{i}(0\leq i\leq N-1)$ can be devided into subsets all of whose elements can be
unified iff is k-colorable.
The width of each level is as follows.
$f_{i}$

$i$

$j$

$gj$

$g_{i}$$f_{i}$$\square$$f_{j}$$g_{i}$

$k$

$G$

1.

$1\leq$level $\leq 4logN$

width(level)$\leq 2^{level-}$. Especially, width(level) $\leq N^{4}/2$ when level $=4logN$ .

2. level $=4logN+1$

nodes in this level, some of which can be unified. In case $i=j=p=N-1$ ,There are$N$
there arefunctions of the form $x_{4logN+1}\cdot x_{4logN+2}\cdot g_{a}+\overline{x_{5logN+1}\cdot x_{5logN+2}}\cdot f_{N-1},0\leq$$a\leq N-1$ . Therefore, the functions differ only when $x_{4logN+1}=x_{4logN+2}=1$ . From
Lemma 1, these $N$ nodes can be reduced to nodes.
$N^{4}$$k$

Otherwise, for at least one assignment to $x_{4logN+1}$ and $x_{41ogN+2}$ , different functions are
selected among$0<a<N-1$ . From proposition 1, the functions cannot be unified.
$f_{a},$

Hence, width $(4logN+1)=N^{4}-N+k$ . The following discussions show that we may
minimize the width in this level.

3. level $=4logN+2$$0\leq a,$functions of the form
In this level, there are$N-1$ and functions of the form $\overline{x_{4logN+2}}\cdot f_{N-1}+x_{4logN+2}\cdot h_{c},$ $0\leq c\leq k$ , where. The former ones cannot be unified each other. The latterones can be unified with one of the former functions from Proposition 4. Therefore,
width $(4logN+2)=N^{2}$ .
$N^{2}$$\overline{x_{4logN+2}}\cdot f_{a}+x_{4logN+2}\cdot f_{b},$$b\leq$$k$$h_{c}=u\{g_{i_{1}}, g_{i_{2}}, \cdots g_{i_{m}}\}$

Even though the width is not minimized in level $4logN+1$ , the width of this level isby the same argument.

$N^{2}$

4. Ievel $=4logN+3$

As is the case of 3, width $(4logN+3)=N$ .
5. $4logN+4<$ level $\leq 6logN+2$

In general, the width of a level is at most twice the width of the preceding level. Therefore
width(level) $\leq N\cross 2^{level-4logN-3}\leq N^{3}$ .
As $N^{4}-N+k>N^{4}/2\geq 3/2N^{3}$ for $N\geq 2$ , the width of this BDD is $N^{4}-N+k$ .
The proof shows that it is still NP-complete to minimize the width of a specified level.
Theorem 2 MINIMUM BDD IDENTIFICATION is NP-complete.

$\square$247
Proof We can easily see that MINIMUM BDD IDENTIFICATION is in NP by extending
Algorithm MinIdent. For the proof of NP-hardness, we use a reduction from GRAPH KCOLORABILITY. The basic idea of this proof is similar to that of Theorem 1.
The Boolean function of the reduced problem has $7logN+4$ variables. The set of examples
are as follows :} $(r<s)$ ,$\langle B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot B_{m}\cdot*000\cdot B_{r}\cdot B_{s},$$f_{i}(r, s)$$\langle B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot B_{m}\cdot*001\cdot B_{r}\cdot B_{s},$$f_{j}(r, s)$} $(r<s)$ ,,$(r<s)$ ,$\{B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot B_{m}\cdot*010\cdot B_{r}\cdot B_{s}, f_{p}(r, s)\}(r<s)$$\{B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot B_{m}\cdot*011\cdot B_{r}\cdot B_{s},$$f_{q}(r, s)\rangle$$\langle B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot B_{m}\cdot 0100\cdot B_{r}\cdot B_{s},$$f_{m}(r, s)$$\langle B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot B_{m}\cdot 1100\cdot B_{r}\cdot B_{s},$$g_{m}(r, s)$$\langle B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot B_{m}\cdot 0101\cdot B_{r}\cdot B_{s},$$f_{0}(r, s)$} $(r<s)$ ,} $(r<s, (r, s)\in E)$ ,} $(r<s)$ ,$\langle B_{i}\cdot B_{j}\cdot B_{p}\cdot B_{q}\cdot B_{m}\cdot 1101\cdot B_{r}\cdot B_{s} , f_{1}(r, s)\rangle(r<s)$,

where $0\leq i,j,p.q.m,$ $S\leq N-1and*means$ both and 1.
and, –,are the same as those defined in the proof of Theorem 1. The positive integer to bound thenumber of nodes is $3N^{5}+(k+2)N^{4}-2$ .
The number of examples is
11 $N^{5}(N-1)+2|E|N^{4}=O(N^{6})$ .
To count the number of nodes, we must remove redundant nodes from the width of eachlevel.
The minimum number of nodes in each level, denoted by node(level), is as follows.
$0\leq i\leq N$ be devided into
Let be k’-colorable, that is,subsets,$1\leq l\leq k’$ s.t. all the elements ofcan be unified. Thenof the examples canbe substituted by. We claim that, in this case, the minimum numberof nodes can be realized at the same time for level $\leq 5logN+5$ .
$0$$7^{\cdot},$$G$$f_{0},$$f_{1},$$\cdots,$$k’$$g_{i},$$G_{l}$$.f_{N-1}$$g_{N-1}$$g_{0},$ $g_{1}$$G_{l}=\{g_{l_{1}},g\iota_{2}, \cdots g_{l_{m}}\}$$g_{l_{1}},g_{l_{2}}\cdots g_{l_{m}}$$h_{l}=u\{g_{l_{1}}, g_{l_{2}}, \cdots g_{l_{m}}\}$

1.

$1\leq$level $\leq 5logN+1$

nodes and any two nodes cannot be unified. Therefore, node(level)
There arelevel-1.
total
node(level) $=2N^{5}-1$ .
2Thenumber of nodes is$N^{5}$$=$$\sum_{1\leq level\leq 5logN+1}$

2. level $=5logN+2$
are fixed and $x_{5logN+1}=1$ , there are $N$ functions which differ only when$x_{5logN+2}=1.x_{5logN+3}=x_{5iogN+4}=0$ . They can be reduced tofunctions iff
is k-colorable. In any other cases, the nodes in this level cannot be unified. Hence
node $(5logN+2)=N^{5}+kN^{4}$ iff is k-colorable.

When $i,j,p,$

$q$

$G$

$k$

$G$

3. level $=5logN+3$

In this level, there are$N^{4}$

different functions of the form$\overline{x_{5logN+3}}\cdot\overline{x_{5logN+4}}\cdot.f_{a}+\overline{x_{5logN+3}}$$x_{5logN+4}\cdot f_{b}+x_{5logN+3}\cdot\overline{x_{5logN+4}}\cdot f_{c}+x_{5logN+3}\cdot x_{5logN+4}\cdot.f_{d}$.

$0\leq a,$ $b,$ $c,$ $d\leq.

N-1$ andfunctions of the form
. The
former ones cannot be unified each other. Among them,nodes can be removed as
redundant nodes. The latter ones can be unified with the former ones from Proposition
4. Therefore. for any G. node $(5logN+3)=N^{4}-N^{2}$ .
$k$$\overline{x_{5logN+3}}\cdot\overline{x_{5logN+4}}\cdot h_{a}+\overline{x_{5logN+3}}\cdot x_{5logN+4}\cdot.f_{1},0\leq a\leq k$$N^{2}$

248
4. level $=5logN+4$

As is the case of 3, node $(51ogN+4)=N^{2}-N$ .
5. $5logn+5\leq$ level $\leq 7logN+4$

node $(5logN+5)=N$ . Then the total number of nodes is less than$N^{3}-N$ .
From the above discussion, when
least

$G$

$\Sigma_{1\leq i\leq 2logN}N\cdot 2^{i-1}=$

is exactly k-colorable, the total number of nodes is at$num_{\min}(N, k)$$=(2N^{5}-1)+(N^{5}+kN^{4})+(N^{4}-N^{2})+(N^{2}-N)+N$$=3N^{5}+(k+1)N^{4}-1$

and is not more than$num_{\max}(N, k)$$=(2N^{5}-1)+(N^{5}+kN^{4})+(N^{4}-N^{2})+(N^{2}-N)+(N^{3}-N)$$=3N^{5}+(k+1)N^{4}+N^{3}-2N-1$ .
As $num_{\min}(N, k+1)>3N^{5}+(k+2)N^{4}-2>num_{\max}(N, k)$ , the number of nodes is lessthan $3N^{5}+(k+2)N^{4}-2$ .

3.2$\square$Hardness of Learning Binary Decision Diagrams

The identification of the minimum BDD from examples is closely related to computational
learning theory. On the PAC-learning model $[9, 10]$ , the goal is to find a good approximation ofan unknown Boolean function from random examples. When the learner requests an example,. The error of a hypothesis
it is drawn according to an arbitrary distribution on
for unknown is defined to be the probability that $f(x)\neq g(x)$ for an assignment $x\in\{0,1\}^{n}$drawn randomly according to .
We call that a Boolean function is learnable by a class $X$ of concepts iff there is a learningalgorithm that runs in polynomial time and outputs, with probability at least. a hypothesisthat approximates the unknown Boolean function with error at most .
From Theorem 1 and 2, we can make the same discussion as [11] on the learnability of
k-width BDD and k-node BDD. If there is a polynomial time learning algorithm, we can solve
GRAPH K-COLORABILITY using the learning algorithm and the examples shown in the
reduction, which implies NP $=RP$ .
Corollary 1 k-width BDD and k-node BDD are not learnable under PAC-learning model
unless NP $=RP$ .
We note that k-decision tree, a tree representation of a Boolean function. is learnable inpolynomial time.
$P$$\{0,1\}^{n}$

$g$

$f$

$P$

$1-\delta$$\epsilon$

4Conclusion

In this paper, we proved the NP-completeness of identifying the minimum BDD. The results
also imply the hardness of learning k-width BDD and k-node BDD. It is our future work to249
consider the case when we allow to change the variable ordering because the size of a BDD
greatly varies according to the variable ordering.

References[1] S. B. Akers:“Binary Decision Diagrams”, IEEE Trans. Comput. Vol.C-27, No.6, pp.509516 (1978).
[2] R. E. Bryant : “ Graph-based Algorithms for Boolean Function Manipulation”, IEEE
Trans. Comput. Vol.C35, No.8, pp.677-691 (1986).
[3] R. E. Bryant :“ On the Complexity of VLSI Implementations and Graph Representationsof Boolean Functions with Application to Integer Multiplication”, IEEE Trans. Comput,
Vol.40, No.2, pp.205-213 (1991).
[4] H. T. Liaw and C. S. Lin:’ On the OBDD-Representation of General Boolean Functions“,IEEE Trans. Comput.. Vol.41, No.6, pp.661-664 (1992).
[5] N. Ishiura and S. Yajima : A Class of Logic Functions Expressible by PolynomialSize Binary Decision Diagrams, Proc. of the Synthesis and Simulation Meeting andInternational Interchange 90, pp.48-54 (1990).
’[6] H. Sawada, Y. Takenaga and S. Yajima: On the Relations between Binary Decision Diagrams, Turing machines and Combinational Logic Circuits”, Technical Report of IEICE,COMP92-66, pp.49-56 (1992).
[7] D. Sieling and I. Wegener: “ NC-Algorithm for Operations on Binary Decision Diagrams”,
Parallel Processing Letters (to appear).
[8] Y. Takenaga and S. Yajima :“On the Complexity of Boolean Operations Using Binary
Decision $Diagrams$ , Technical Report of IEICE, COMP91-86, pp.21-26 (1992).

[9] L. G. Valiant :“ A Theory of the Learnable”, Comm. ACM, Vol.27, No.ll, pp.1134-1142(1984).

[10] M. Kearns, M. Li, L. Pitt and L.G. Valiant :“ On the Learnability of Boolean Formulae’,Proc. 19th STOC, pp.285-295 (1987).
[11] L. Pitt and L. G. Valiant :“Computational Limitations on Learning from Examples”, J.
ACM, Vol.35, No.4, pp.965-984 (1988).
[12] N. Ishiura : Synthesis of Multi-level Logic Circuits from Binary Decision Diagrams”,
Proc. Synthesis and Simulation Meeting and International Interchange 92. pp.74-83(1992).