Data complexity in the εℒ family of description logics

Adila Alfa Krisnadhi, Carsten Lutz

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

49 Citations (Scopus)

Abstract

We study the data complexity of instance checking and conjunctive query answering in the ε Lscr; family of description logics, with a particular emphasis on the boundary of tractability. We identify a large number of intractable extensions of ε Lscr;, but also show that in εℒI f, the extension of ε ℒ with inverse roles and global functionality, conjunctive query answering is tractable regarding data complexity. In contrast, already instance checking in ε ℒ extended with only inverse roles or global functionality is EXPTIME-complete regarding combined complexity.

Original languageEnglish
Title of host publicationLogic for Programming, Artificial Intelligence, and Reasoning - 14th International Conference, LPAR 2007, Proceedings
Pages333-347
Number of pages15
Publication statusPublished - 1 Dec 2007
Event14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2007 - Yerevan, Armenia
Duration: 15 Oct 200719 Oct 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4790 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2007
Country/TerritoryArmenia
CityYerevan
Period15/10/0719/10/07

Fingerprint

Dive into the research topics of 'Data complexity in the εℒ family of description logics'. Together they form a unique fingerprint.

Cite this