Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1359581, author = {Bendík, Jaroslav and Beneš, Nikola and Černá, Ivana and Barnat, Jiří}, address = {Dagstuhl, Germany}, booktitle = {Foundations of Software Technology and Theoretical Computer Science - 36th International Conference, FSTTCS 2016}, doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.50}, edition = {65}, editor = {Akash Lal, S. Akshay, Saket Saurabh, Sandeep Sen}, keywords = {Minimal unsatisfiable subsets; Maximal satisfiable subsets; Unsatisfiability analysis; Infeasibility analysis}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Dagstuhl, Germany}, isbn = {978-3-95977-027-9}, pages = {661-673}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, title = {Tunable Online MUS/MSS Enumeration}, year = {2016} }
TY - JOUR ID - 1359581 AU - Bendík, Jaroslav - Beneš, Nikola - Černá, Ivana - Barnat, Jiří PY - 2016 TI - Tunable Online MUS/MSS Enumeration PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany SN - 9783959770279 KW - Minimal unsatisfiable subsets KW - Maximal satisfiable subsets KW - Unsatisfiability analysis KW - Infeasibility analysis N2 - 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. ER -
BENDÍK, Jaroslav, Nikola BENEŠ, Ivana ČERNÁ a Jiří BARNAT. Tunable Online MUS/MSS Enumeration. In Akash Lal, S. Akshay, Saket Saurabh, Sandeep Sen. \textit{Foundations of Software Technology and Theoretical Computer Science - 36th International Conference, FSTTCS 2016}. 65. vyd. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016, s.~661-673. ISBN~978-3-95977-027-9. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.50.
|