{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T04:12:21Z","timestamp":1730002341609,"version":"3.28.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p>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 &gt; 0 there is an ontology and query that are k-Exp-hard in data complexity.<\/jats:p>","DOI":"10.24963\/kr.2024\/50","type":"proceedings-article","created":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T06:30:28Z","timestamp":1729924228000},"page":"531-541","source":"Crossref","is-referenced-by-count":0,"title":["Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster"],"prefix":"10.24963","author":[{"given":"Carsten","family":"Lutz","sequence":"first","affiliation":[{"name":"Department of Computer Science, Leipzig University, Germany"}]},{"given":"Quentin","family":"Mani\u00e8re","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Leipzig University, Germany"},{"name":"Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI), Dresden\/Leipzig, Germany"}]}],"member":"10584","event":{"name":"21st International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}","theme":"Artificial Intelligence","location":"Hanoi, Vietnam","acronym":"KR-2024","number":"21","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2024,11,1]]},"end":{"date-parts":[[2024,11,8]]}},"container-title":["Proceedings of the TwentyFirst International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T06:30:38Z","timestamp":1729924238000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2024\/50"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2024\/50","relation":{},"subject":[],"published":{"date-parts":[[2024,11]]}}}