Abstract: Almost the same types of restricted branching programs (or binary decision diagrams BDDs) are considered in complexity theory and in applications like hardware verification. These models are read-once branching programs (free BDDs) and certain types of oblivious branching programs (ordered and indexed BDDs with k layers). The complexity of the satisfiability problem for these restricted branching programs is investigated and tight hierarchy results are proved for the classes of functions representable by k layers of ordered or indexed BDDs of polynomial size.
Publication Year: 1998
Publication Date: 1998-09-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 36
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot