Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Weight in Enumeration
Jönköping University, Jönköping International Business School, JIBS, Informatics.
2017 (English)In: Language and Automata Theory and Applications / [ed] Frank DrewesCarlos, Martín-Vide, Bianca Truthe, Springer, 2017, p. 208-219Conference paper, Published paper (Refereed)
Abstract [en]

In our setting enumeration amounts to generate all solutions of a problem instance without duplicates. We address the problem of enumerating the models of B-formulæ. A B-formula is a propositional formula whose connectives are taken from a fixed set B of Boolean connectives. Without imposing any specific order to output the solutions, this task is solved. We completely classify the complexity of this enumeration task for all possible sets of connectives B imposing the orders of (1) non-decreasing weight, (2) non-increasing weight; the weight of a model being the number of variables assigned to 1. We consider also the weighted variants where a non-negative integer weight is assigned to each variable and show that this add-on leads to more sophisticated enumeration algorithms and even renders previously tractable cases intractable, contrarily to the constraint setting. As a by-product we obtain also complexity classifications for the optimization problems known as  MIN-ONESMIN-ONES  and  MAX-ONESMAX-ONES  which are in the B-formula setting two different tasks.

Place, publisher, year, edition, pages
Springer, 2017. p. 208-219
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10168
Keywords [en]
Computational complexity, Enumeration, Non-decreasing weight, Polynomial delay, Post’s lattice, MaxOnes
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:hj:diva-35525DOI: 10.1007/978-3-319-53733-7_15ISI: 000418579700015ISBN: 978-3-319-53732-0 (print)ISBN: 978-3-319-53733-7 (electronic)OAI: oai:DiVA.org:hj-35525DiVA, id: diva2:1095821
Conference
LATA 2017, 11th International Conference on Language and Automata Theory and Applications, Umeå, 6-9 March, 2017.
Available from: 2017-05-16 Created: 2017-05-16 Last updated: 2018-01-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Schmidt, Johannes

Search in DiVA

By author/editor
Schmidt, Johannes
By organisation
JIBS, Informatics
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 68 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf