Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Complexity of branching temporal description logics

Gutierrez Basulto, Victor ORCID: https://orcid.org/0000-0002-6117-5459, Jung, Jean Christoph and Lutz, Carsten 2012. Complexity of branching temporal description logics. Presented at: 20th European Conference on Artificial Intelligence, ECAI 2012, Montpellier, France, 27-31 Aug 2012. Frontiers in Artificial Intelligence and Applications. , vol.242 IOS Press, pp. 390-395. 10.3233/978-1-61499-098-7-390

[thumbnail of FAIA242-0390.pdf]
Preview
PDF - Published Version
Available under License Creative Commons Attribution Non-commercial.

Download (265kB) | Preview

Abstract

We study branching-time temporal description logics (TDLs) based on the DLs ALC and EL and the temporal logics CTL and CTL*. The main contributions are algorithms for satisfiability that are more direct than existing approaches, and (mostly) tight elementary complexity bounds that range from PTIME to 2EXPTIME and 3EXPTIME. A careful use of tree automata techniques allows us to obtain transparent and uniform algorithms, avoiding to deal directly with the intricacies of CTL*.

Item Type: Conference or Workshop Item (Paper)
Date Type: Publication
Status: Published
Schools: Computer Science & Informatics
Publisher: IOS Press
ISBN: 9781614990970
Date of First Compliant Deposit: 5 June 2018
Last Modified: 23 Oct 2022 13:52
URI: https://orca.cardiff.ac.uk/id/eprint/111953

Citation Data

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

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics