ALC_ALC: A context description logic

Klarman, Szymon and Gutierrez Basulto, Victor ORCID: https://orcid.org/0000-0002-6117-5459 2010. ALC_ALC: A context description logic. Presented at: Logics in Artificial Intelligence - 12th European Conference, JELIA 2010, Helsinki, Finland, September 13-15, 2010. Logics in Artificial Intelligence. Lecture Notes in Computer Science. Lecture Notes in Computer Science Berlin, Heidelberg: Springer, 10.1007/978-3-642-15675-5_19

Preview

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

Abstract

We develop a novel description logic (DL) for representing and reasoning with contextual knowledge. Our approach descends from McCarthy’s tradition of treating contexts as formal objects over which one can quantify and express first-order properties. As a foundation we consider several common product-like combinations of DLs with multimodal logics and adopt the prominent (Kn)ALC. We then extend it with a second sort of vocabulary for describing contexts, i.e., objects of the second dimension. In this way, we obtain a two-sorted, two-dimensional combination of a pair of DLs ALC, called ALCALC. As our main technical result, we show that the satisfiability problem in this logic, as well as in its proper fragment (Kn)ALC with global TBoxes and local roles, is 2ExpTime- complete. Hence, the surprising conclusion is that the significant increase in the expressiveness of ALCALC due to adding the vocabulary comes for no substantial price in terms of its worst-case complexity.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	Springer
ISBN:	978-3-642-15674-8
ISSN:	0302-9743
Date of First Compliant Deposit:	5 June 2018
Last Modified:	23 Oct 2022 13:52
URI:	https://orca.cardiff.ac.uk/id/eprint/111970

Citation Data

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

Actions (repository staff only)

Edit Item