Query Answering in Propositional Circumscription

Query Answering in Propositional Circumscription

Mario Alviano

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1669-1675. https://doi.org/10.24963/ijcai.2018/231

Propositional circumscription defines a preference relation over the models of a propositional theory, so that models being subset-minimal on the interpretation of a set of objective atoms are preferred.The complexity of several computational tasks increase by one level in the polynomial hierarchy due to such a preference relation;among them there is query answering, which amounts to decide whether there is an optimal model satisfying the query.A complete algorithm for query answering is obtained by searching for a model, not necessarily an optimal one, that satisfies the query, and such that no model unsatisfying the query is more preferred.If the query or its complement are among the objective atoms, the algorithm has a simpler behavior, which is also described in the paper.Moreover, an incomplete algorithm is obtained by searching for a model satisfying both the query and an objective atom being unit-implied by the theory extended with the complement of the query.A prototypical implementation is tested on instances from the 2nd International Competition on Computational Models of Argumentation (ICCMA'17).
Keywords:
Knowledge Representation and Reasoning: Non-classical Logics for Knowledge Representation
Knowledge Representation and Reasoning: Computational Models of Argument