COMPLETENESS AND NON-COMPLETENESS RESULTS WITH RESPECT TO READ-ONCE PROJECTIONS

Citation
B. Bollig et I. Wegener, COMPLETENESS AND NON-COMPLETENESS RESULTS WITH RESPECT TO READ-ONCE PROJECTIONS, Information and computation, 143(1), 1998, pp. 24-33
Citations number
10
Categorie Soggetti
Mathematics,"Computer Science Information Systems",Mathematics,"Computer Science Information Systems
Journal title
ISSN journal
08905401
Volume
143
Issue
1
Year of publication
1998
Pages
24 - 33
Database
ISI
SICI code
0890-5401(1998)143:1<24:CANRWR>2.0.ZU;2-T
Abstract
Several models of restricted branching programs or binary decision dia grams have a lot of applications in hardware verification. These model s are investigated here from a complexity theoretical viewpoint. Becau se of depth restrictions projections are not suitable as reduction typ e and have to be restricted to read-once projections. Several types of polynomial-size binary decision diagrams have complete problems with respect to polynomial read-once projections. On the contrary it can be proved that the classes of polynomial-size decision trees and polynom ial-size read-once branching programs or free binary decision diagrams do not have such complete problems. (C) 1998 Academic Press.