Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

An ASP-Based Framework for MUSes

Created by
  • Haebom

Author

Mohimenul Kabir, Kuldeep S Meel

Outline

This paper proposes a new framework, MUS-ASP, to efficiently find the minimal unsatisfiable subset (MUS), which is important for understanding the root cause of the impossibility of unsatisfiable logic formulas. A MUS is a minimal set of clauses that maintains the impossibility. Existing studies have focused on two directions: enumerating as many MUS as possible within a given time limit or counting the total number of MUS for a given impossible logic formula. MUS-ASP is based on Answer Set Programming (ASP) and solves the MUS enumeration problem by leveraging the knowledge representation capability of ASP. Experimental results show that MUS-ASP is efficient in MUS enumeration and computation, especially when integrated with a hybrid solver.

Takeaways, Limitations

Takeaways:
We present an ASP-based MUS enumeration framework, MUS-ASP, which enables more efficient MUS enumeration and calculation than existing methods.
In particular, it shows improved performance through integration with hybrid solvers.
Effectively solve complex combinatorial problems by leveraging ASP's knowledge representation capabilities.
Limitations:
In this paper, we do not evaluate the performance of MUS-ASP on various types of impossible logic formulas and may be limited to certain types of problems.
Since it depends on the performance of the ASP system, limitations of the ASP system may affect the performance of MUS-ASP.
A more in-depth comparative analysis with other MUS enumeration algorithms is needed.
👍