Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
Open Access
- 1 November 2024
- conference paper
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 21 (1) , 531-541
Abstract
We study extensions of expressive decidable fragments of first-order logic with circumscription, considering in particular the two-variable fragment FO^2, its extension C^2 with counting quantifiers, and the guarded fragment GF. We prove that if only unary predicates are minimized (or fixed) during circumscription, then decidability of logical consequence is preserved. For FO^2 the complexity increases from NExp to NExp^NP-complete, for GF it (remarkably!) increases from 2Exp to Tower-complete, and for C^2 it remains open. We also consider querying circumscribed knowledge bases whose ontology is a GF sentence, showing that the problem is decidable for unions of conjunctive queries, Tower-complete in combined complexity, and elementary in data complexity. Already for atomic queries and ontologies that are sets of guarded existential rules, however, for every k > 0 there is an ontology and query that are k-Exp-hard in data complexity.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Complexity Hierarchies beyond ElementaryACM Transactions on Computation Theory, 2016
- Guarded NegationJournal of the ACM, 2015
- A new semantics for overriding in description logicsArtificial Intelligence, 2015
- A non-monotonic Description Logic for reasoning about typicalityArtificial Intelligence, 2013
- Querying the Guarded Fragment2010
- Deciding Boolean Algebra with Presburger ArithmeticJournal of Automated Reasoning, 2006
- Description logics of minimal knowledge and negation as failureACM Transactions on Computational Logic, 2002
- On the Restraining Power of GuardsThe Journal of Symbolic Logic, 1999
- Modal Languages and Bounded Fragments of Predicate LogicJournal of Philosophical Logic, 1998
- Embedding defaults into terminological knowledge representation formalismsJournal of Automated Reasoning, 1995