Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance

Abstract

Ordered binary decision diagrams with repeated tests are considered both in complexity theory and in applications. Bollig et al. have proved in [B. Bollig, M. Sauerhoff, D. Sieling, I. Wegener, Hierarchy theorems of kOBDDs and kIBDDs, Theoret. Comput. Sci. 205 (1998) 45-60] a tight hierarchy result for the classes of functions representable by k layers of polynomial-size deterministic ordered binary decision diagrams. In this paper the nondeterministic case is investigated, where the layers are driven by one and the same variable ordering. For k being a constant, it is shown that for the existential, the parity-, and the majority acceptance mode the analogous hierarchy collapses. (c) 2005 Elsevier B.V. All rights reserved.