Publication: Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
| dc.bibliographiccitation.firstpage | 6 | |
| dc.bibliographiccitation.issue | 1 | |
| dc.bibliographiccitation.journal | Information Processing Letters | |
| dc.bibliographiccitation.lastpage | 10 | |
| dc.bibliographiccitation.volume | 98 | |
| dc.contributor.author | Brosenne, H. | |
| dc.contributor.author | Homeister, M. | |
| dc.contributor.author | Waack, S. | |
| dc.date.accessioned | 2018-11-07T09:58:42Z | |
| dc.date.available | 2018-11-07T09:58:42Z | |
| dc.date.issued | 2006 | |
| dc.description.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. | |
| dc.identifier.doi | 10.1016/j.ipl.2005.11.011 | |
| dc.identifier.isi | 000235725400002 | |
| dc.identifier.uri | https://resolver.sub.uni-goettingen.de/purl?gro-2/37424 | |
| dc.notes.status | zu prüfen | |
| dc.notes.submitter | Najko | |
| dc.publisher | Elsevier Science Bv | |
| dc.relation.issn | 0020-0190 | |
| dc.title | Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance | |
| dc.type | journal_article | |
| dc.type.internalPublication | yes | |
| dc.type.peerReviewed | yes | |
| dc.type.status | published | |
| dspace.entity.type | Publication |