Applications and Extensions of PTIME Description Logics with Functional Constraints
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 948-953.
Abstract
We review and extend earlier work on the logic CFD, a description logic that allows terminological cycles with universal restrictions over functional roles. In particular, we consider the problem of reasoning about concept subsumption and the problem of computing certain answers for a family of attribute-connected conjunctive queries, showing that both problems are in PTIME. We then consider the effect on the complexity of these problems after adding a concept constructor that expresses concept union, or after adding a concept constructor for the bottom class. Finally, we show that adding both constructors makes both problems EXPTIME-complete.David Toman, Grant Weddell
@inproceedings{ijcai2009p161,
title = {Applications and Extensions of PTIME Description Logics with Functional Constraints},
author = {Toman, David and Weddell, Grant E.},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {948--953},
year = {2009},
url = {https://ijcai.org/proceedings/2009/161},
}
TY - CPAPER TI - Applications and Extensions of PTIME Description Logics with Functional Constraints AU - Toman, David AU - Weddell, Grant E. T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 948 EP - 953 UR - https://ijcai.org/proceedings/2009/161 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
