@INPROCEEDINGS{Hustadt+Motik+Sattler@IJCAI2005,
 AUTHOR        = {Hustadt, Ullrich and Motik, Boris and Sattler, Ulrike},
 TITLE         = {Data Complexity of Reasoning in Very Expressive 
 Description Logics},
 BOOKTITLE     = {Proceedings of the Nineteenth International 
 Joint Conference on Artificial Intelligence (IJCAI 2005)
 [Edinburg, Scotland, 30 July - 5 August 2005]},
 YEAR          = {2005},
 PAGES         = {466-471},
 PUBLISHER     = {International Joint Conferences on
 Artificial Intelligence},
 CADDRESS      = {Edinburgh, Scotland},
 CYEAR         = {2005},
 CMONTH        = jul # {~30--} # aug # {~5},
 URL           = {http://www.ijcai.org/papers/0326.pdf},
 ABSTRACT      = {<em>Data complexity</em> of reasoning in description logics
 (DLs) estimates the performance of reasoning algorithms
 measured in the size of the ABox only.
 We show that, even for the very expressive DL
 SHIQ, satisfiability checking is data complete for
 NP. For applications with large ABoxes, this can
 be a more accurate estimate than the usually considered
 combined complexity, which is EXPTIMEcomplete.
 Furthermore, we identify an expressive
 fragment, Horn-SHIQ, which is data complete for P, 
 thus being very appealing for practical usage.}
}

{"_id":"MpBQF7wJ5WBCWqH36","bibbaseid":"hustadt-motik-sattler-datacomplexityofreasoninginveryexpressivedescriptionlogics-2005","author_short":["Hustadt, U.","Motik, B.","Sattler, U."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Hustadt"],"firstnames":["Ullrich"],"suffixes":[]},{"propositions":[],"lastnames":["Motik"],"firstnames":["Boris"],"suffixes":[]},{"propositions":[],"lastnames":["Sattler"],"firstnames":["Ulrike"],"suffixes":[]}],"title":"Data Complexity of Reasoning in Very Expressive Description Logics","booktitle":"Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI 2005) [Edinburg, Scotland, 30 July - 5 August 2005]","year":"2005","pages":"466-471","publisher":"International Joint Conferences on Artificial Intelligence","caddress":"Edinburgh, Scotland","cyear":"2005","cmonth":"July 30–August 5","url":"http://www.ijcai.org/papers/0326.pdf","abstract":"<em>Data complexity</em> of reasoning in description logics (DLs) estimates the performance of reasoning algorithms measured in the size of the ABox only. We show that, even for the very expressive DL SHIQ, satisfiability checking is data complete for NP. For applications with large ABoxes, this can be a more accurate estimate than the usually considered combined complexity, which is EXPTIMEcomplete. Furthermore, we identify an expressive fragment, Horn-SHIQ, which is data complete for P, thus being very appealing for practical usage.","bibtex":"@INPROCEEDINGS{Hustadt+Motik+Sattler@IJCAI2005,\n AUTHOR = {Hustadt, Ullrich and Motik, Boris and Sattler, Ulrike},\n TITLE = {Data Complexity of Reasoning in Very Expressive \n Description Logics},\n BOOKTITLE = {Proceedings of the Nineteenth International \n Joint Conference on Artificial Intelligence (IJCAI 2005)\n [Edinburg, Scotland, 30 July - 5 August 2005]},\n YEAR = {2005},\n PAGES = {466-471},\n PUBLISHER = {International Joint Conferences on\n Artificial Intelligence},\n CADDRESS = {Edinburgh, Scotland},\n CYEAR = {2005},\n CMONTH = jul # {~30--} # aug # {~5},\n URL = {http://www.ijcai.org/papers/0326.pdf},\n ABSTRACT = {<em>Data complexity</em> of reasoning in description logics\n (DLs) estimates the performance of reasoning algorithms\n measured in the size of the ABox only.\n We show that, even for the very expressive DL\n SHIQ, satisfiability checking is data complete for\n NP. For applications with large ABoxes, this can\n be a more accurate estimate than the usually considered\n combined complexity, which is EXPTIMEcomplete.\n Furthermore, we identify an expressive\n fragment, Horn-SHIQ, which is data complete for P, \n thus being very appealing for practical usage.}\n}\n","author_short":["Hustadt, U.","Motik, B.","Sattler, U."],"key":"Hustadt+Motik+Sattler@IJCAI2005","id":"Hustadt+Motik+Sattler@IJCAI2005","bibbaseid":"hustadt-motik-sattler-datacomplexityofreasoninginveryexpressivedescriptionlogics-2005","role":"author","urls":{"Paper":"http://www.ijcai.org/papers/0326.pdf"},"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"http://cgi.csc.liv.ac.uk/~ullrich/publications/all.bib?authorFirst=1","dataSources":["WhiGijHmCtTSdLaAj","FgmYE34DdKWThg2dR"],"keywords":[],"search_terms":["data","complexity","reasoning","very","expressive","description","logics","hustadt","motik","sattler"],"title":"Data Complexity of Reasoning in Very Expressive Description Logics","year":2005}