On the Undecidability of the Situation Calculus Extended with Description Logic Ontologies
Authors: Diego Calvanese, Giuseppe De Giacomo, Mikhail Soutchanski
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we investigate situation calculus action theories extended with ontologies, expressed as description logics TBoxes that act as state constraints. We show that this combination, while natural and desirable, is particularly problematic: it leads to undecidability of the simplest form of reasoning, namely satisfiability, even for the simplest kinds of description logics and the simplest kind of situation calculus action theories. The aim of this paper is to investigate how deep this problem really is. To do so, we consider a simplified setting... Here we show that in the above setting the simplest form of reasoning, namely satisfiability, the minimal requirement for any logical theory, is undecidable, even when the state constraints are expressed in the simplest description logics, such as DL-Litecore, and the situation calculus action theory is of the simplest form, namely context free in the sense of [Reiter, 1991] and local effect [Vassos et al., 2008]. |
| Researcher Affiliation | Academia | Diego Calvanese Free University of Bozen-Bolzano Bolzano, Italy calvanese@inf.unibz.it Giuseppe De Giacomo Sapienza Universit a di Roma Roma, Italy degiacomo@dis.uniroma1.it Mikhail Soutchanski Ryerson University Toronto, Canada mes@cs.ryerson.ca |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation. Therefore, there is no mention of publicly available datasets or access information. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments involving data. Therefore, there is no mention of training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not implement or rely on specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not involve experimental setups with specific hyperparameter values or training configurations. |