Brosenne, H.H.BrosenneHomeister, M.M.HomeisterWaack, S.S.Waack2018-11-072018-11-072006https://resolver.sub.uni-goettingen.de/purl?gro-2/37424Ordered 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.journal_article10.1016/j.ipl.2005.11.011000235725400002