On the relation between structured d-DNNFs and SDDs

Simple item page
dc.contributor.authorBollig, Beate
dc.contributor.authorFarenholtz, Martin
dc.date.accessioned2021-03-12T11:19:45Z
dc.date.available2021-03-12T11:19:45Z
dc.date.issued2020-08-17
dc.description.abstractStructured 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.en
dc.identifier.urihttp://hdl.handle.net/2003/40080
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-21957
dc.language.isoende
dc.relation.ispartofseriesTheory Comput Syst;65(2)
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectComplexity theoryen
dc.subjectDecomposable negation normal formsen
dc.subjectKnowledge compilationen
dc.subjectSentential decision diagramsen
dc.subject.ddc004
dc.subject.rswkKomplexitätstheoriede
dc.subject.rswkNormalformde
dc.subject.rswkEntscheidungsgraphde
dc.titleOn the relation between structured d-DNNFs and SDDsen
dc.typeTextde
dc.type.publicationtypearticlede
dcterms.accessRightsopen access
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primarycitationBollig, B., Farenholtz, M. On the Relation Between Structured d-DNNFs and SDDs. Theory Comput Syst 65, 274–295 (2021).de
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1007/s00224-020-10003-yde

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Bollig-Farenholtz2021_Article_OnTheRelationBetweenStructureD.pdf
Size:
630.54 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

LS 02 Komplexitätstheorie und Effiziente Algorithmen