Tunable Online MUS/MSS Enumeration
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00091546" target="_blank" >RIV/00216224:14330/16:00091546 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.50" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.50</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.50" target="_blank" >10.4230/LIPIcs.FSTTCS.2016.50</a>
Alternative languages
Result language
angličtina
Original language name
Tunable Online MUS/MSS Enumeration
Original language description
In various areas of computer science, the problem of dealing with a set of constraints arises. If the set of constraints is unsatisfiable, one may ask for a minimal description of the reason for this unsatisifiability. Minimal unsatisfiable subsets (MUSes) and maximal satisfiable subsets (MSSes) are two kinds of such minimal descriptions. The goal of this work is the enumeration of MUSes and MSSes for a given constraint system. As such full enumeration may be intractable in general, we focus on building an online algorithm, which produces MUSes/MSSes in an on-the-fly manner as soon as they are discovered. The problem has been studied before even in its online version. However, our algorithm uses a novel approach that is able to outperform the current state-of-the-art algorithms for online MUS/MSS enumeration. Moreover, the performance of our algorithm can be adjusted using tunable parameters. We evaluate the algorithm on a set of benchmarks.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Foundations of Software Technology and Theoretical Computer Science - 36th International Conference, FSTTCS 2016
ISBN
9783959770279
ISSN
1868-8969
e-ISSN
—
Number of pages
13
Pages from-to
661-673
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Chennai, India
Event date
Dec 8, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—