Data complexity in the εℒ family of description logics

Adila Alfa Krisnadhi, Carsten Lutz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

48 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
CountryArmenia
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

    Krisnadhi, A. A., & Lutz, C. (2007). Data complexity in the εℒ family of description logics. In Logic for Programming, Artificial Intelligence, and Reasoning - 14th International Conference, LPAR 2007, Proceedings (pp. 333-347). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4790 LNAI).