{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:12Z","timestamp":1753889772480,"version":"3.41.2"},"reference-count":44,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,2,27]],"date-time":"2012-02-27T00:00:00Z","timestamp":1330300800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We propose a novel, type-elimination-based method for reasoning in the\ndescription logic SHIQbs including DL-safe rules. To this end, we first\nestablish a knowledge compilation method converting the terminological part of\nan ALCIb knowledge base into an ordered binary decision diagram (OBDD) which\nrepresents a canonical model. This OBDD can in turn be transformed into\ndisjunctive Datalog and merged with the assertional part of the knowledge base\nin order to perform combined reasoning. In order to leverage our technique for\nfull SHIQbs, we provide a stepwise reduction from SHIQbs to ALCIb that\npreserves satisfiability and entailment of positive and negative ground facts.\nThe proposed technique is shown to be worst case optimal w.r.t. combined and\ndata complexity and easily admits extensions with ground conjunctive queries.<\/jats:p>","DOI":"10.2168\/lmcs-8(1:12)2012","type":"journal-article","created":{"date-parts":[[2012,9,6]],"date-time":"2012-09-06T10:03:11Z","timestamp":1346925791000},"source":"Crossref","is-referenced-by-count":7,"title":["Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog"],"prefix":"10.46298","volume":"Volume 8, Issue 1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1609-2080","authenticated-orcid":false,"given":"Sebastian","family":"Rudolph","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9172-2601","authenticated-orcid":false,"given":"Markus","family":"Kr\u00f6tzsch","sequence":"additional","affiliation":[]},{"given":"Pascal","family":"Hitzler","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,2,27]]},"reference":[{"key":"10.2168\/LMCS-8(1:12)2012_dlhandbook","doi-asserted-by":"crossref","unstructured":"Baader, F., Calvanese, D., McGuinness, D., Nardi, D., and Patel-Schneider, P., editors (2007).The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2nd edition.","DOI":"10.1017\/CBO9780511711787"},{"key":"10.2168\/LMCS-8(1:12)2012_blackburn","doi-asserted-by":"crossref","unstructured":"Blackburn, P., de Rijke, M., and Venema, Y. (2001).Modal Logic. Cambridge University Press.","DOI":"10.1017\/CBO9781107050884"},{"key":"10.2168\/LMCS-8(1:12)2012_borgida-dl-fol-96","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(96)00004-5"},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:journals\/jar\/CalvaneseGLLR07","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9078-x"},{"key":"10.2168\/LMCS-8(1:12)2012_DL-98-alc","unstructured":"Calvanese, D., DeGiacomo, G., and Rosati, R. (1998). A note on encoding inverse roles and functional restrictions inALCknowledge bases. InProceedings of the 11th International Workshop on Description Logic (DL'98), pages 69-71. CEUR."},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:conf\/aaai\/CalvaneseEO07","unstructured":"Calvanese, D., Eiter, T., and Ortiz, M. (2007b). Answering regular path queries in expressive description logics: An automata-theoretic approach. InProceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI'07), pages 391-396. AAAI Press."},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:journals\/csur\/DantsinEGV01","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:conf\/aaai\/GiacomoL94","unstructured":"DeGiacomo, G. and Lenzerini, M. (1994). Boosting the correspondence between description logics and propositional dynamic logics. InIn Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI'94), pages 205-212. AAAI Press."},{"key":"10.2168\/LMCS-8(1:12)2012_disjDatalog","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:conf\/wollic\/EiterLOS09","doi-asserted-by":"crossref","unstructured":"Eiter, T., Lutz, C., Ortiz, M., and Simkus, M. (2009). Query answering in description logics: The knots approach. In Ono, H., Kanazawa, M., and de Queiroz, R. J. G. B., editors,Proceedings of the 16th International Workshop on Logic, Language, Information and Computation (WoLLIC'09), volume 5514 ofLecture Notes in Computer Science, pages 26-36. Springer.","DOI":"10.1007\/978-3-642-02261-6_3"},{"key":"10.2168\/LMCS-8(1:12)2012_Fitting","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2360-3"},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:conf\/ijcai\/GlimmHLS07","unstructured":"Glimm, B., Horrocks, I., Lutz, C., and Sattler, U. (2007). Conjunctive query answering for the description logicSHIQ. In Veloso, M. M., editor,Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07), pages 399-404."},{"key":"10.2168\/LMCS-8(1:12)2012_GradelOR97","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Otto, M., and Rosen, E. (1997). Two-variable logic with counting is decidable. InProceedings of the 12th Annual IEEE Symposium on Logic in Computer Science (LICS'97), pages 306-317. IEEE Computer Society.","DOI":"10.1109\/LICS.1997.614957"},{"key":"10.2168\/LMCS-8(1:12)2012_fost","doi-asserted-by":"crossref","unstructured":"Hitzler, P., Kr\u00f6tzsch, M., and Rudolph, S. (2009).Foundations of Semantic Web Technologies. Chapman & Hall\/CRC.","DOI":"10.1201\/9781420090512"},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:journals\/jar\/HustadtMS07","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9080-3"},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:journals\/iandc\/HustadtMS08","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.11.006"},{"key":"10.2168\/LMCS-8(1:12)2012_Hustadt:2000:IDD:647938.741235","doi-asserted-by":"crossref","unstructured":"Hustadt, U. and Schmidt, R. A. (2000). Issues of decidability for description logics in the framework of resolution. In Caferra, R. and Salzer, G., editors,Automated Deduction in Classical and Non-Classical Logics, Selected Papers, volume 1761 ofLecture Notes in Computer Science, pages 191-205. Springer.","DOI":"10.1007\/3-540-46508-1_13"},{"key":"10.2168\/LMCS-8(1:12)2012_huth","unstructured":"Huth, M. R. A. and Ryan, M. D. (2000).Logic in Computer Science: Modelling and reasoning about systems. Cambridge University Press."},{"key":"10.2168\/LMCS-8(1:12)2012_kazakov08:sroiqcompl","unstructured":"Kazakov, Y. (2008).RIQandSROIQare harder thanSHOIQ. In Brewka, G. and Lang, J., editors,Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR'08), pages 274-284. AAAI Press."},{"key":"10.2168\/LMCS-8(1:12)2012_kazakov09-cdreasoning","unstructured":"Kazakov, Y. (2009). Consequence-driven reasoning for HornSHIQontologies. In Boutilier, C., editor,Proceedings of the 21st International Conference on Artificial Intelligence (IJCAI'09), pages 2040-2045. IJCAI."},{"key":"10.2168\/LMCS-8(1:12)2012_KKS11:parallEL","unstructured":"Kazakov, Y., Kr\u00f6tzsch, M., and Siman\u00c4\u008d\u00edk, F. (2011). Concurrent classification ofELontologies. In Aroyo, L., Welty, C., Alani, H., Taylor, J., Bernstein, A., Kagal, L., Noy, N., and Blomqvist, E., editors,Proceedings of the 10th International Semantic Web Conference (ISWC'11), volume 7032 ofLNCS. Springer."},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:conf\/kr\/KontchakovLTWZ10","unstructured":"Kontchakov, R., Lutz, C., Toman, D., Wolter, F., and Zakharyaschev, M. (2010). The combined approach to query answering in DL-lite. In Lin, F., Sattler, U., and Truszczynski, M., editors,Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR'10). AAAI Press."},{"key":"10.2168\/LMCS-8(1:12)2012_KRH:HornDLs12","unstructured":"Kr\u00f6tzsch, M., Rudolph, S., and Hitzler, P. (2012). Complexities of {Horn description logics.ACM Trans. Comp. Log.To appear; preprint available at http:\/\/tocl.acm.org\/accepted.html."},{"key":"10.2168\/LMCS-8(1:12)2012_lutz01complexity","unstructured":"Lutz, C. and Sattler, U. (2001). The complexity of reasoning with boolean modal logics. In Wolter, F., Wansing, H., de Rijke, M., and Zakharyaschev, M., editors,Advances in Modal Logics Volume 3. CSLI Publications, Stanford."},{"key":"10.2168\/LMCS-8(1:12)2012_Lutz-et-al-IANDC-05","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.11.002"},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:journals\/jancl\/LutzW05","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.15.189-213"},{"key":"10.2168\/LMCS-8(1:12)2012_Motik:PhD","unstructured":"Motik, B. (2006).Reasoning in Description Logics using Resolution and Deductive Databases. PhD thesis, Universit\u00e4t Karlsruhe (TH), Germany."},{"key":"10.2168\/LMCS-8(1:12)2012_kaon2","doi-asserted-by":"crossref","unstructured":"Motik, B. and Sattler, U. (2006). A comparison of reasoning techniques for querying large description logic ABoxes. In Hermann, M. and Voronkov, A., editors,Proceedings of the 13th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR'06), volume 4246 ofLecture Notes in Computer Science, pages 227-241. Springer.","DOI":"10.1007\/11916277_16"},{"key":"10.2168\/LMCS-8(1:12)2012_DLsafe-JWS","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.05.001"},{"key":"10.2168\/LMCS-8(1:12)2012_hermit","unstructured":"Motik, B., Shearer, R., and Horrocks, I. (2009). Hypertableau Reasoning for Description Logics.Journal of Artificial Intelligence Research, 36:165-228."},{"key":"10.2168\/LMCS-8(1:12)2012_pansattlervardi","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.169-207"},{"key":"10.2168\/LMCS-8(1:12)2012_popkorn","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511983382"},{"key":"10.2168\/LMCS-8(1:12)2012_pratt","doi-asserted-by":"crossref","unstructured":"Pratt, V. R. (1979). Models of program logics. In20th Annual Symposium on Foundations of Computer Science, pages 115-122. IEEE.","DOI":"10.1109\/SFCS.1979.24"},{"key":"10.2168\/LMCS-8(1:12)2012_PH:C2complex","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-005-5791-1"},{"key":"10.2168\/LMCS-8(1:12)2012_DBLP:conf\/rweb\/Rudolph11","doi-asserted-by":"crossref","unstructured":"Rudolph, S. (2011). Foundations of description logics. In Polleres, A., d'Amato, C., Arenas, M., Handschuh, S., Kroner, P., Ossowski, S., and Patel-Schneider, P. F., editors,Reasoning Web. Semantic Technologies for the Web of Data - 7th International Summer School 2011, Tutorial Lectures, volume 6848 ofLecture Notes in Computer Science, pages 76-136. Springer.","DOI":"10.1007\/978-3-642-23032-5_2"},{"key":"10.2168\/LMCS-8(1:12)2012_RKH:Jelia-08","doi-asserted-by":"crossref","unstructured":"Rudolph, S., Kr\u00f6tzsch, M., and Hitzler, P. (2008a). Cheap Boolean role constructors for description logics. In H\u00f6lldobler, S., Lutz, C., and Wansing, H., editors,Proceedings of the 11th European Conference on Logics in Artificial Intelligence (JELIA'08), volume 5293 ofLecture Notes in Computer Science, pages 362-374. Springer.","DOI":"10.1007\/978-3-540-87803-2_30"},{"key":"10.2168\/LMCS-8(1:12)2012_RKH:OBBD08b","doi-asserted-by":"crossref","unstructured":"Rudolph, S., Kr\u00f6tzsch, M., and Hitzler, P. (2008b). Description logic reasoning with decision diagrams: CompilingSHIQto disjunctive datalog. In Sheth, A., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T., and Thirunarayan, K., editors,Proceedings of the 7th International Semantic Web Conference (ISWC'08), volume 5318 ofLecture Notes in Computer Science, pages 435-450. Springer.","DOI":"10.1007\/978-3-540-88564-1_28"},{"key":"10.2168\/LMCS-8(1:12)2012_RKH-08-OBDDs","unstructured":"Rudolph, S., Kr\u00f6tzsch, M., and Hitzler, P. (2008c). Terminological reasoning inSHIQwith ordered binary decision diagrams. InProceedings of the 23rd National Conference on Artificial Intelligence (AAAI 2008), pages 529-534. AAAI Press."},{"key":"10.2168\/LMCS-8(1:12)2012_schild91:correspondence","unstructured":"Schild, K. (1991). A correspondence theory for terminological logics: Preliminary report. In Mylopoulos, J. and Reiter, R., editors,Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI'91), pages 466-471. Morgan Kaufmann."},{"key":"10.2168\/LMCS-8(1:12)2012_ALBO","doi-asserted-by":"crossref","unstructured":"Schmidt, R. A. and Tishkovsky, D. (2007). Using tableau to decide expressive description logics with role negation. In Aberer, K., Choi, K.-S., Noy, N. F., Allemang, D., Lee, K.-I., Nixon, L. J. B., Golbeck, J., Mika, P., Maynard, D., Mizoguchi, R., Schreiber, G., and Cudr\u00e9-Mauroux, P., editors,The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference (ISWC'07 + ASWC'07), volume 4825 ofLecture Notes in Computer Science, pages 438-451. Springer.","DOI":"10.1007\/978-3-540-76298-0_32"},{"key":"10.2168\/LMCS-8(1:12)2012_conf\/ijcai\/Simancik11","unstructured":"Siman\u00c4\u008d\u00edk, F., Kazakov, Y., and Horrocks, I. (2011). Consequence-based reasoning beyond Horn ontologies. In Walsh, T., editor,Proceedings of the 22nd International Conference on Artificial Intelligence (IJCAI'11), pages 1093-1098. AAAI Press\/IJCAI."},{"key":"10.2168\/LMCS-8(1:12)2012_Tobies:PhD","unstructured":"Tobies, S. (2001).Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, RWTH Aachen, Germany."},{"key":"10.2168\/LMCS-8(1:12)2012_owl2-overview","unstructured":"W3C OWL Working Group (27 October 2009).OWL 2 Web Ontology Language: Document Overview. W3C Recommendation. Available at http:\/\/www.w3.org\/TR\/owl2-overview\/."},{"key":"10.2168\/LMCS-8(1:12)2012_Wegener04bdds","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00297-X"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/806\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/806\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:56:32Z","timestamp":1681242992000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/806"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,27]]},"references-count":44,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(1:12)2012","relation":{"references":[{"id-type":"doi","id":"10.1016\/j.ic.2007.11.006","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1202.0914","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1202.0914","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,2,27]]},"article-number":"806"}}