✦ LIBER ✦

Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

✍ Scribed by Beate Bollig; Ingo Wegener

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 262 KB
Volume: 61
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.2000.1733

No coin nor oath required. For personal study only.

✦ Synopsis

Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, and computer aided design. For many functions it is easy to estimate the OBDD size but asymptotically optimal bounds are only known in simple situations. In this paper, methods for proving asymptotically optimal bounds are presented and applied to the solution of some basic problems concerning OBDDs. The largest size increase by a synthesis step of ?-OBDDs followed by an optimal reordering is determined as well as the largest ratio of the size of deterministic finite automata, quasi-reduced OBDDs, and zero-suppressed BDDs compared to the size of OBDDs. Moreover, the worst case OBDD size of functions with a given number of 1-inputs is investigated. 2000

📜 SIMILAR VOLUMES

Probabilistic analysis of an asymptotica

Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

✍ C.T. Ng; X. Cai; T.C.E. Cheng 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB 👁 2 views

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well-known NP-hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optima

The Method of Multiple Scales: Asymptoti

The Method of Multiple Scales: Asymptotic Solutions and Normal Forms for Nonlinear Oscillatory Problems

✍ NESTOR E. SANCHEZ 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 442 KB

The method of multiple scales is implemented in Maple V Release 2 to generate a uniform asymptotic solution O( r ) for a weakly nonlinear oscillator. In recent work, it has been shown that the method of multiple scales also transforms the differential equations into normal form, so the given algorit

A novel continuous genetic algorithm for

A novel continuous genetic algorithm for the solution of optimal control problems

✍ Zaer S. Abo-Hammour; Ali Ghaleb Asasfeh; Adnan M. Al-Smadi; Othman M. K. Alsmadi 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB

A Fast, High-Order Algorithm for the Sol

A Fast, High-Order Algorithm for the Solution of Surface Scattering Problems: Basic Implementation, Tests, and Applications

✍ Oscar P. Bruno; Leonid A. Kunyansky 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 255 KB

On the asymptotic solution of the Graetz

On the asymptotic solution of the Graetz-Nusselt problem for short x → 0 and large x → ∞ with partial usage of finite differences

✍ Antonio Campo 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

On the combination of some semi-discreti

On the combination of some semi-discretization methods and boundary integral equations for the numerical solution of initial boundary value problems

✍ R. Chapko 📂 Article 📅 2002 🏛 John Wiley and Sons ⚖ 95 KB 👁 2 views