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
Issue Date: 2020-08-17
Rights link:
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
Bollig-Farenholtz2021_Article_OnTheRelationBetweenStructureD.pdf630.54 kBAdobe PDFView/Open

This item is protected by original copyright

This item is licensed under a Creative Commons License Creative Commons