Title :
Least upper bounds on OBDD sizes
Author :
Heap, Mark A. ; Mercer, M.R.
Author_Institution :
Dept. of Electr. & Comput. Eng., Texas Univ., Austin, TX, USA
fDate :
6/1/1994 12:00:00 AM
Abstract :
This paper derives exact equations for the maximum number of nonterminal vertexes in reduced and quasi-reduced ordered binary decision diagrams (OBDD´s). A reduced OBDD is reduced by both merging and deleting vertices, and a quasi-reduced OBDD is reduced only by merging. These formulas are used to tighten Lee´s original bounds, and to correct the bounds recently reported by H.T. Liaw and C.S. Lin (1992)
Keywords :
Boolean functions; decoding; OBDD sizes; exact equations; least upper bounds; nonterminal vertexes; reduced ordered binary decision diagrams; Automata; Circuit testing; Computational modeling; Error correction; Error correction codes; Hardware; Iterative decoding; Merging; Programmable logic arrays; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on
