Symbolic verification of Boolean constraints over partially specified functions

Incomplete or partial specifications arise out of mistakes in design or purposefully to avoid loss of generality in application. When designing a system with several partially specified functions, we often impose constraints on the global behavior of the system. In this paper we study the problem of verifying whether a set of partially specified functions meets such constraints. We show that the problem is Π₂ ^P complete. While symbolic BDD-based algorithms have been widely used for propositional satifiability (Σ₁ ^P complete) and validity (Π₁^P complete) problems, the structure of BDDs is not natural for solving Π₂^P complete problems. We present a two-step BDD-based method for solving the above Π₂^P complete problem and show that the method is effective when the number of functions is small