Authors: | Bollig, Beate Farenholtz, Martin |
Title: | On the relation between structured d-DNNFs and SDDs |
Language (ISO): | en |
Abstract: | Structured d-DNNFs and SDDs are restricted negation normal form circuits used in knowledge compilation as target languages into which propositional theories are compiled. Structuredness is imposed by so-called vtrees. By definition SDDs are restricted structured d-DNNFs. Beame and Liew (2015) as well as Bova and Szeider (2017) mentioned the question whether structured d-DNNFs are really more general than SDDs w.r.t. polynomial-size representations (w.r.t. the number of Boolean variables the represented functions are defined on.) The main result in the paper is the proof that a function can be represented by SDDs of polynomial size if the function and its complement have polynomial-size structured d-DNNFs that respect the same vtree. |
Subject Headings: | Complexity theory Decomposable negation normal forms Knowledge compilation Sentential decision diagrams |
Subject Headings (RSWK): | Komplexitätstheorie Normalform Entscheidungsgraph |
URI: | http://hdl.handle.net/2003/40080 http://dx.doi.org/10.17877/DE290R-21957 |
Issue Date: | 2020-08-17 |
Rights link: | https://creativecommons.org/licenses/by/4.0/ |
Appears in Collections: | LS 02 Komplexitätstheorie und Effiziente Algorithmen |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Bollig-Farenholtz2021_Article_OnTheRelationBetweenStructureD.pdf | 630.54 kB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is licensed under a Creative Commons License