TY - GEN
T1 - Data complexity in the εℒ family of description logics
AU - Krisnadhi, Adila Alfa
AU - Lutz, Carsten
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=38349006924&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:38349006924
SN - 9783540755586
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 333
EP - 347
BT - Logic for Programming, Artificial Intelligence, and Reasoning - 14th International Conference, LPAR 2007, Proceedings
T2 - 14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2007
Y2 - 15 October 2007 through 19 October 2007
ER -