Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: 18th RCRA International Workshop on “Experimental evaluation of algorithms for solving problems with combinatorial explosion”
Article type: Research Article
Authors: Belov, Anton | Lynce, Inês | Marques-Silva, Joao; ;
Affiliations: CSI/CASL, University College Dublin, Dublin, Ireland. E-mails: {anton.belov, jpms}@ucd.ie | IST/INESC-ID, Technical University of Lisbon, Lisbon, Portugal. E-mail: ines@sat.inesc-id.pt
Note: [] Corresponding author: J. Marques-Silva, CASL, University College Dublin, Dublin, Ireland. E-mail: jpms@ucd.ie.
Abstract: Minimally Unsatisfiable Subformulas (MUS) find a wide range of practical applications, including product configuration, knowledge-based validation, and hardware and software design and verification. MUSes also find application in recent Maximum Satisfiability algorithms and in CNF formula redundancy removal. Besides direct applications in Propositional Logic, algorithms for MUS extraction have been applied to more expressive logics. This paper proposes two algorithms for computation of MUSes of propositional formulas in Conjunctive Normal Form (CNF). The first algorithm is optimal in its class, meaning that it requires the smallest number of calls to a SAT solver. The second algorithm extends earlier work, but implements a number of new techniques. Among these, this paper analyzes in detail the technique of recursive model rotation, which provides significant performance gains in practice. Experimental results, obtained on representative practical benchmarks, indicate that the new algorithms achieve significant performance gains with respect to state of the art MUS extraction algorithms.
Keywords: Boolean satisfiability, minimally unsatisfiable subformula
DOI: 10.3233/AIC-2012-0523
Journal: AI Communications, vol. 25, no. 2, pp. 97-116, 2012
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl