Model enumeration in propositional circumscription via unsatisfiable core analysis*. Issue 5 (22nd August 2017)

• Record Type: Journal Article
• Authors: ALVIANO, MARIO
• Editors: Rocha, Ricardo; Cao Son, Tran
• Is Part Of: Theory and practice of logic programming. Volume 17:Issue 5/6(2017)
• Page Start: 708
• Page End: 725
• Publication Date: 2017-08-22
• Subjects: Circumscription, -- minimal model enumeration, -- minimal correction subsets, -- minimal intervention strategies, -- unsatisfiable core analysis; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068417000278
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: Many practical problems are characterized by a preference relation over admissible solutions, where preferred solutions are minimal in some sense. For example, a preferred diagnosis usually comprises a minimal set of reasons that is sufficient to cause the observed anomaly. Alternatively, a minimal correction subset comprises a minimal set of reasons whose deletion is sufficient to eliminate the observed anomaly. Circumscription formalizes such preference relations by associating propositional theories with minimal models. The resulting enumeration problem is addressed here by means of a new algorithm taking advantage of unsatisfiable core analysis. Empirical evidence of the efficiency of the algorithm is given by comparing the performance of the resulting solver, circumscriptino, withhclasp, camus_mcs, lbx andmcsls on the enumeration of minimal models for problems originating from practical applications.