For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Computational Power of Binary Decision Diagrams
Hiroshi SAWADA Yasuhiko TAKENAGA Shuzo YAJIMA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/06/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata, Languages and Theory of Computing
binary decision diagram, on-line Turing machine, planer circuit, permutation, complete language,
Full Text: PDF(640.9KB)>>
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 clas DL of languages accepted by log-space bounded deterministic Turing machines. From the results, we can see that the problem whether U-PolyBDD U-NC1 is equivalent to a famous open problem whether DL U-NC1, where U-NC1 is the class of languages accepted by uniform families of log-depth constant fan-in logic circuits.