×

zbMATH — the first resource for mathematics

On the evolution of the worst-case OBDD size. (English) Zbl 1003.68050
Summary: We prove matching lower and upper bounds on the worst-case OBDD size of a Boolean function, revealing an interesting oscillating behavior.

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Software:
CUDD
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Breitbart, Y.; Hunt III, H.; Rosenkrantz, D., On the size of binary decision diagrams representing Boolean functions, Theoret. comput. sci., Vol. 145, 45-69, (1995) · Zbl 0874.68283
[2] Brace, K.S.; Rudell, R.L.; Bryant, R.E., Efficient implementation of a BDD package, (), 40-45
[3] Bryant, R.E., Graph-based algorithms for Boolean function manipulation, IEEE trans. comput., Vol. C-35, 8, 677-691, (1986) · Zbl 0593.94022
[4] Bryant, R.E., Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM comput. surv., Vol. 24, 3, 293-318, (1992)
[5] Gröpl, C., Binary decision diagrams for random Boolean functions, (1999), Humboldt Universität zu Berlin, Available via http://dochost.rz.hu-berlin.dc/docserv.html · Zbl 1023.94022
[6] Gröpl, C.; Srivastav, A.; Prömel, H.J., Size and structure of random ordered binary decision diagrams (extended abstract), (), 238-248
[7] Gröpl, C.; Srivastav, A.; Prömel, H.J., Size and structure of random ordered binary decision diagrams, (2000), Preprint, 30 pp.
[8] Gergov, J.; Meinel, C., Efficient Boolean manipulation with OBDDs can be extended to fbdds, IEEE trans. comput., Vol. 43, 10, 1197-1209, (1994) · Zbl 1063.68573
[9] Heap, M.A.; Mercer, M.R., Least upper bounds on OBDD sizes, IEEE trans. comput., Vol. 43, 6, 764-767, (1994) · Zbl 1033.68682
[10] Lee, C.Y., Representation of switching circuits by binary decision programs, Bell system techn. J., Vol. 38, 985-999, (1959) · Zbl 0222.94042
[11] Liaw, H.-T.; Lin, C.-S., On the OBDD-representation of general Boolean functions, IEEE trans. comput., Vol. 41, 6, 661-664, (1992) · Zbl 1395.94400
[12] Shannon, C.E., The synthesis of two-terminal switching circuits, Bell system techn. J., Vol. 28, 59-98, (1949)
[13] F. Somenzi, CUDD: Colorado University Decision Diagram Package, available via ftp://vlsi.colorado.edu/pub/
[14] Sieling, D.; Wegener, I., Graph driven BDDs—A new data structure for Boolean functions, Theoret. comput. sci., Vol. 141, 283-310, (1995) · Zbl 0873.68036
[15] Wegener, I., The size of reduced OBDDs and optimal Read-once branching programs for almost all Boolean functions, IEEE trans. comput., Vol. 43, 11, 1262-1269, (1994) · Zbl 1068.68685
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.