On the Undecidability of the Situation Calculus Extended with Description Logic Ontologies
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 2840-2845.
Abstract
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.
Diego Calvanese, Giuseppe De Giacomo, and Mikhail Soutchanski. 2015. On the Undecidability of the Situation Calculus Extended with Description Logic Ontologies. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 2840–2845. https://ijcai.org/proceedings/2015/402
Calvanese, D., De Giacomo, G., & Soutchanski, M. (2015). On the Undecidability of the Situation Calculus Extended with Description Logic Ontologies. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 (pp. 2840–2845). IJCAI. https://ijcai.org/proceedings/2015/402
@inproceedings{ijcai2015p402,
title = {On the Undecidability of the Situation Calculus Extended with Description Logic Ontologies},
author = {Calvanese, Diego and De Giacomo, Giuseppe and Soutchanski, Mikhail},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {2840--2845},
year = {2015},
month = {7},
note = {Special Track on Knowledge Representation and Reasoning},
url = {https://ijcai.org/proceedings/2015/402},
}
TY - CPAPER TI - On the Undecidability of the Situation Calculus Extended with Description Logic Ontologies AU - Calvanese, Diego AU - De Giacomo, Giuseppe AU - Soutchanski, Mikhail T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 2840 EP - 2845 UR - https://ijcai.org/proceedings/2015/402 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
