---
title: "Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes"
authors:
  - "Víctor Gutiérrez-Basulto"
  - "Jean Christoph Jung"
  - "Thomas Schneider"
doi: ""
url: "https://ijcai.org/proceedings/2015/426"
pdf: "https://ijcai.org/proceedings/2015/0426.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "3015-3020"
track: "Special Track on Knowledge Representation and Reasoning"
keywords:
---

# Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes

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

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, 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.