A Class of Logic Functions Expressible by a Polynomial-Size Binary Decision Diagram

概要

論文の詳細を見る
Binary Decision Diagram(BDD)is an expression form of logic functions. Besides the existence of a unique canonical form for each logic function, many practical functions can be expressed by a BD. of feasible size. It is easily shown that the size of a BDD to express a logic function is in the worst case exponential to the number of input variables, but there have been very few discussions on the problem what kind of logic functions are expressed by a BDD of feasible size. In order to make this point clear, in this paper, we define a class of logic functions which is expressible by a BDD whose size is bounded by apolynomial of the number of input variables, and we investigate the properties of the logic functions of this class. Especially we focus on relations between BDD's and Turing machines.
一般社団法人情報処理学会の論文
1989-10-16