Abstract
We introduce a BDD with redundant variables as an Indexed BDD (IBDD) and define PolyIBDD as the class of Boolean functions represented by polynomial-sized IBDDs for the number of input variables. Assuming that the class of languages on {0, 1}* that are accepted by logarithmic space bounded DTMs is DLOG, the following relation holds. PolyIBDD = DLOG. That is to say that languages which belong to DLOG also belong to PolyIBDD. We also show examples of polynomial-sized IBDD's construction from logarithmic space bounded DTMs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S.B. Akers, “Binary Decision Diagrams,” IEEE Trans. Comput., Vol. C-27, No. 6, pp. 509–516, June 1978.
B. Plessier, G. Hachtel, and F. Somenzi, “Extended BDDs: Trading Off Canonicity for Structure in Verification Algorithms,” Formal Methods in System Design, Vol. 4, No. 2, pp. 167–185, Feb. 1994.
R.E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Trans. Comput., Vol. C-35, No. 8, pp. 677–691, Aug. 1986.
R.E. Bryant, “On the complexity of VLSI implementations and graph representations of boolean functions with application to integer multiplication,” IEEE Trans. Comput., Vol. 40, No. 2, pp. 205–213, Feb. 1991.
J.R. Burch, “Using BDDs to verify multipliers,” Proc. 28th Design Automation Conference, pp. 408–412, June 1991.
N. Ishiura and S. Yajima, “A class of logic functions expressible by a polynomial-size binary decision diagram,” Proc. Synthesis and Simulation Meeting and International Interchange (SASIMI '90), Oct. 1990, pp. 48–54.
J. Jain, J. Bitner, M. Abadir, J.A. Abraham, and D.S. Fussel, “Efficent representation and verification of multiplier using IBDDs,” Technical Report CAD 325-91, MCC, 1991.
J. Jain, M. Abadir, J. Bitner, D.S. Fussel, and J.A. Abraham, “IBDDs: An efficent functional representation for digital circuits,” Proc. European Design Automation Conference, Mar. 1992, pp. 440–446.
Y. Lai and S. Sastry, “Edge-valued binary decision diagrams for multi-level hierarchical verification,” Proc. 29th Design Automation Conference, June 1992, pp. 608–613.
W.L. Ruzzo, “On uniform circuit complexity,” J. Computer and System Sciences, Vol. 22, pp. 365–383, 1981.
S. Minato, N. Ishiura, and S. Yajima, “Shared binary decision diagrams with attributed edges for efficient boolean function manipulation,” Proc. 27th Design Automation Conference, June 1990, pp. 52–57.
H. Sawada, “Computational power of binary decision diagrams,” Master's thesis, Kyoto Univ., Mar. 1993.
H. Yasuura, “Design and analysis of hardware algorithms,” in Design Methodologies, Advances in CAD for VLSI, S. Goto (Ed.), North-Holland, pp. 185–214, 1986.
H. Yasuura and S. Yajima, “Hardware Algorithms for VLSI Systems,” VLSI Engineering, Lecture Notes in Computer Science 163, Springer-Verlag, 1984, pp. 105–129.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Yamada, T., Yasuura, H. On the computational power of binary decision diagram with redundant variables. Form Method Syst Des 8, 65–89 (1996). https://doi.org/10.1007/BF00121263
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00121263