Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes

Gutiérrez-Basulto, Víctor; Jung, Jean Christoph; Schneider, Thomas

Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes

Víctor Gutiérrez-Basulto, Jean Christoph Jung, Thomas Schneider

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 3015-3020.

Abstract

We study temporal description logics (TDLs) based on the branching-time temporal logic CTL and the lightweight DL EL in the presence of rigid roles and restricted TBoxes. While TDLs designed in this way are known to be inherently nonelementary or even undecidable over general TBoxes, there is hope for a better computational behaviour over acyclic or empty TBoxes. We begin by showing that the basic DL ALC combined with CTL in the described way is indeed decidable, but still inherently nonelementary. As our main contribution, we identify several TDLs of elementary complexity, obtained by combining EL with CTL fragments that allow only restricted sets of temporal operators. We obtain upper complexity bounds ranging from PTime to coNExpTime and mostly tight lower bounds. This contrasts the fact that the respective ALC variants are already inherently nonelementary.

Víctor Gutiérrez-Basulto, Jean Christoph Jung, and Thomas Schneider. 2015. Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 3015–3020. https://ijcai.org/proceedings/2015/426

@inproceedings{ijcai2015p426,
  title     = {Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes},
  author    = {Gutiérrez-Basulto, Víctor and Jung, Jean Christoph and Schneider, Thomas},
  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     = {3015--3020},
  year      = {2015},
  month     = {7},
  note      = {Special Track on Knowledge Representation and Reasoning},
  url       = {https://ijcai.org/proceedings/2015/426},
}

TY  - CPAPER
TI  - Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes
AU  - Gutiérrez-Basulto, Víctor
AU  - Jung, Jean Christoph
AU  - Schneider, Thomas
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 3015
EP  - 3020
UR  - https://ijcai.org/proceedings/2015/426
ER  -