1. Eldorado
  2. Fakultäten
  3. 04 Fakultät für Informatik
  4. LS 02 Komplexitätstheorie und Effiziente Algorithmen
Full metadata record
DC FieldValueLanguage
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.identifier.urihttp://hdl.handle.net/2003/40080-
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-21957-
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.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.titleOn the relation between structured d-DNNFs and SDDsen
dc.typeTextde
dc.type.publicationtypearticlede
dc.subject.rswkKomplexitätstheoriede
dc.subject.rswkNormalformde
dc.subject.rswkEntscheidungsgraphde
dcterms.accessRightsopen access-
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1007/s00224-020-10003-yde
eldorado.secondarypublication.primarycitationBollig, B., Farenholtz, M. On the Relation Between Structured d-DNNFs and SDDs. Theory Comput Syst 65, 274–295 (2021).de
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

View License
Show simple item record


This item is licensed under a Creative Commons License Creative Commons