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
|
Preview |
PDF
- Published Version
Available under License Creative Commons Attribution Non-commercial. Download (265kB) | Preview |
Official URL: https://doi.org/10.3233/978-1-61499-098-7-390
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: | 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 7 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
 |
Edit Item |
Altmetric
Altmetric