Finding a Collection of MUSes Incrementally

被引：18

作者：

Bacchus, Fahiem ^{[1
]}

Katsirelos, George ^{[2
]}

机构：

[1] Univ Toronto, Dept Comp Sci, Toronto, ON, Canada

[2] INRA, MIAT, Toulouse, France

来源：

INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING, CPAIOR 2016 | 2016年 / 9676卷

关键词：

MINIMAL UNSATISFIABLE SUBSETS;

D O I：

10.1007/978-3-319-33954-2_3

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Minimal Unsatisfiable Sets (MUSes) are useful in a number of applications. However, in general there are many different MUSes, and each application might have different preferences over these MUSes. Typical MUSER systems produce a single MUS without much control over which MUS is generated. In this paper we describe an algorithm that can efficiently compute a collection of MUSes, thus presenting an application with a range of choices. Our algorithm improves over previous methods for finding multiple MUSes by computing its MUSes incrementally. This allows it to generate multiple MUSes more efficiently; making it more feasible to supply applications with a collection of MUSes rather than just one.

引用

页码：35 / 44

页数：10

共 24 条

[1]

[Anonymous], 2011, MUS TRACK SAT COMPET

[2] Using Minimal Correction Sets to More Efficiently Compute Minimal Unsatisfiable Sets [J].