Lightweight temporal description logics with rigid roles and restricted TBoxes

Gutierrez Basulto, Victor, Jung, Jean Christoph and Schneider:, Thomas 2015. Lightweight temporal description logics with rigid roles and restricted TBoxes. Presented at: Twenty-Fourth International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 25-31 July 2015.

Preview

PDF - Accepted Post-Print Version Download (681kB) | Preview

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.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Completion
Status:	Unpublished
Schools:	Computer Science & Informatics
Related URLs:	http://ijcai.org/Abstract/15/426
Date of First Compliant Deposit:	4 June 2018
Date of Acceptance:	16 April 2015
Last Modified:	16 Aug 2018 16:22
URI:	http://orca.cf.ac.uk/id/eprint/111944

Citation Data

Cited 8 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item