Autor(en): | Bollig, Beate Farenholtz, Martin |
Titel: | On the relation between structured d-DNNFs and SDDs |
Sprache (ISO): | en |
Zusammenfassung: | 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. |
Schlagwörter: | Complexity theory Decomposable negation normal forms Knowledge compilation Sentential decision diagrams |
Schlagwörter (RSWK): | Komplexitätstheorie Normalform Entscheidungsgraph |
URI: | http://hdl.handle.net/2003/40080 http://dx.doi.org/10.17877/DE290R-21957 |
Erscheinungsdatum: | 2020-08-17 |
Rechte (Link): | https://creativecommons.org/licenses/by/4.0/ |
Enthalten in den Sammlungen: | LS 02 Komplexitätstheorie und Effiziente Algorithmen |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
Bollig-Farenholtz2021_Article_OnTheRelationBetweenStructureD.pdf | 630.54 kB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons