Description Logics with Pointwise Circumscription
Authors: Federica Di Stefano, Magdalena Ortiz, Mantas Šimkus
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main positive results are for ontologies in DLs ALCIO and ALCI: we prove that for TBoxes of modal depth 1 (i.e. without nesting of existential or universal quantifiers) standard reasoning problems under pointwise circumscription are (co)NEXPTIME-complete and EXPTIMEcomplete, respectively. Our decidability results are achieved using the mosaic technique [N emeti, 1992]: we show that the existence of a pointwise minimal model can be reduced to checking the existence of a finite family of fragments of models that can be assembled into a model. With a reduction from the domino problem, we prove that under the pointwise semantics reasoning w.r.t. circumscribed ALCIO TBoxes of unbounded depth is undecidable. |
| Researcher Affiliation | Collaboration | 1Institute of Logic and Computation, TU Wien, Austria 2Department of Computing Science, Ume a University, Sweden |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. It presents formal definitions, theorems, and proofs. |
| Open Source Code | No | The paper is theoretical and focuses on logical formalisms and complexity results. There is no mention of releasing source code for the described methodology. |
| Open Datasets | No | The paper is theoretical, focusing on logical formalisms and complexity. It does not involve empirical experiments or the use of datasets for training or evaluation. |
| Dataset Splits | No | The paper is purely theoretical, dealing with logical formalisms and computational complexity. It does not involve any experimental setup that would require training, validation, or test dataset splits. |
| Hardware Specification | No | This paper is theoretical, focusing on logic and complexity theory. It does not describe any empirical experiments that would require specific hardware, and thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical in nature, focused on defining a new logical formalism and analyzing its computational complexity. It does not describe any implemented system or software that would require listing specific software dependencies with version numbers for replication. |
| Experiment Setup | No | The paper is theoretical, focusing on logical formalisms and their computational properties. It does not describe any empirical experiments or their setup, and therefore no hyperparameters or training settings are provided. |