Abstract
Ordered binary decision diagrams (OBDDs) are the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Although many even exponential lower bounds on the OBDD size of Boolean functions are known, there are only few functions where the OBDD size is even asymptotically known exactly. In this paper the exact OBDD sizes of the fundamental functions multiplexer and addition of n-bit numbers are determined.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bollig, B., Range, N., Wegener, I.: Exact OBDD bounds for some fundamental functions. ECCC TR07-049 (2007)
Bollig, B., Wegener, I.: Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems. Journal of Computer and System Sciences 61, 558–579 (2000)
Bryant, R.E.: Graph-based algorithms for Boolean manipulation. IEEE Trans. on Computers 35, 677–691 (1986)
Hromkovič, J.: Communication Complexity and Parallel Computing. Springer, Heidelberg (1997)
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)
Sieling, D., Wegener, I.: NC-algorithms for operations on binary decision diagrams. Parallel Processing Letters 48, 139–144 (1993)
Wegener, I.: Optimal decision trees and one-time-only branching-programs for symmetric Boolean functions. Information and Control 62, 129–143 (1984)
Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner (1987)
Wegener, I.: Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bollig, B., Range, N., Wegener, I. (2008). Exact OBDD Bounds for Some Fundamental Functions. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds) SOFSEM 2008: Theory and Practice of Computer Science. SOFSEM 2008. Lecture Notes in Computer Science, vol 4910. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77566-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-77566-9_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77565-2
Online ISBN: 978-3-540-77566-9
eBook Packages: Computer ScienceComputer Science (R0)