2024/07/30 by Carsten Lutz, Lutz, Carsten, Quentin Manière +1 · 2 citations
Computer Science · #Advanced Algebra and Logic #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2407.20822
openalex publication_date 2024/07/30 · openalex created_date 2024/08/01 · openalex updated_date 2026/07/28
We study extensions of expressive decidable fragments of first-order logic with circumscription, in particular the two-variable fragment FO2, its extension C2 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 FO2 the complexity increases from \textrmcoNexp to \textrmcoNExp^\textrmNP-complete, for GF it (remarkably!) increases from \textrm2Exp to \textrmTower-complete, and for C2 the complexity 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, \textrmTower-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-\textrmExp-hard in data complexity.