On the read-once property of branching programs and CNFs of bounded treewidth
- Submitting institution
-
Birkbeck College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 186
- Type
- D - Journal article
- DOI
-
10.1007/s00453-015-0059-x
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 277
- Volume
- 75
- Issue
- 2
- ISSN
- 0178-4617
- Open access status
- Out of scope for open access requirements
- Month of publication
- September
- Year of publication
- 2015
- URL
-
http://eprints.bbk.ac.uk/id/eprint/15405/
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
0
- Research group(s)
-
1 - Algorithms, Verification and Software
- Citation count
- 7
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Nondeterministic Read-Once Branching Programs (NROBPs) is a representation of Boolean functions generalising several models (FBDD and OBDD) widely used in practice. We show that fixed-parameter size NROBPs cannot represent CNFs of bounded treewidth thus settling an important open question in the area of knowledge compilation. The importance of this result for an applied knowledge representation researcher is that it demonstrates that read-once branching programs are inherently incapable of efficiently representing CNFs of bounded treewidth and hence more powerful methods of representation must be used.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -