Back to Search
Start Over
On Oblivious Branching Programs with Bounded Repetition that Cannot Efficiently Compute CNFs of Bounded Treewidth.
- Source :
-
Theory of Computing Systems . Oct2017, Vol. 61 Issue 3, p755-776. 22p. - Publication Year :
- 2017
-
Abstract
- In this paper we study complexity of an extension of ordered binary decision diagrams (OBDDs) called c-OBDDs on CNFs of bounded (primal graph) treewidth. In particular, we show that for each k ≥ 3 there is a class of CNFs of treewidth k for which the equivalent c-OBDDs are of size Ω( n ). Moreover, this lower bound holds if c-OBDDs are non-deterministic and semantic. Our second result uses the above lower bound to separate the above model from sentential decision diagrams (SDDs). In order to obtain the lower bound, we use a structural graph parameter called matching width. Our third result shows that matching width and pathwidth are linearly related. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 61
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 124638221
- Full Text :
- https://doi.org/10.1007/s00224-016-9714-0