On the Computational Power of Binary Decision Diagrams

概要

論文の詳細を見る
Binary decision diagrams (BDD's) are graph representations of Boolean functions, and at the same time they can be regarded as a computational model. In this paper, we discuss relations between BDD's and other computational models and clarify the computational power of BDD's. BDD's have the property that each variable is examined only once according to a total order of the variables. We characterize families of BDD's by on-line deterministic Turing machines and families of permutations. To clarify the computational power of BDD's, we discuss the difference of the computational power with respect to the way of reading inputs. We also show that the language TADGAP (Topologically Arranged Deterministic Graph Accessibility Problem) is simultaneously complete for both of the class U-PolyBDD of languages accepted by uniform families of polynomial-size BDD's and the class DL of languages accepted by log-space bounded deterministic Turing machines. From the results, we can see that the problem whether U-PolyBDD ⊊ U-NC^1 is equivalent to a famous open problem whether DL ⊊ U-NC^1, where U-NC^1 is the class of languages accepted by uniform families of log-depth constant fan-in logic circuits.
社団法人電子情報通信学会の論文
1994-06-25