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.
|
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: |
|
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 |