{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T22:00:11Z","timestamp":1790546411065,"version":"4.1.0"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031107689","type":"print"},{"value":"9783031107696","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"vor","delay-in-days":212,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>To give concise explanations for a conclusion obtained by reasoning over ontologies, <jats:italic>justifications<\/jats:italic> have been proposed as minimal subsets of an ontology that entail the given conclusion. Even though computing one justification can be done in polynomial time for tractable Description Logics such as <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal{EL}\\mathcal{}^+$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mi>EL<\/mml:mi>\n                      <mml:msup>\n                        <mml:mrow>\n                          <mml:mrow\/>\n                        <\/mml:mrow>\n                        <mml:mo>+<\/mml:mo>\n                      <\/mml:msup>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, computing all justifications is complicated and often challenging for real-world ontologies. In this paper, based on a graph representation of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal{EL}\\mathcal{}^+$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mi>EL<\/mml:mi>\n                      <mml:msup>\n                        <mml:mrow>\n                          <mml:mrow\/>\n                        <\/mml:mrow>\n                        <mml:mo>+<\/mml:mo>\n                      <\/mml:msup>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ontologies, we propose a new set of <jats:italic>inference rules<\/jats:italic> (called H-rules) and take advantage of them for providing a new method of computing all justifications for a given conclusion. The advantage of our setting is that most of the time, it reduces the number of <jats:italic>inferences<\/jats:italic> (generated by H-rules) required to derive a given conclusion. This accelerates the enumeration of justifications relying on these inferences. We validate our approach by running real-world ontology experiments. Our graph-based approach outperforms PULi [14], the state-of-the-art algorithm, in most of cases.<\/jats:p>","DOI":"10.1007\/978-3-031-10769-6_19","type":"book-chapter","created":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T01:02:56Z","timestamp":1659315776000},"page":"310-328","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Hypergraph-Based Inference Rules for\u00a0Computing $$\\mathcal{EL}\\mathcal{}^+$$-Ontology Justifications"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4262-4001","authenticated-orcid":false,"given":"Hui","family":"Yang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yue","family":"Ma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicole","family":"Bidoit","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,8,1]]},"reference":[{"key":"19_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-319-40970-2_32","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2016","author":"MF Arif","year":"2016","unstructured":"Arif, M.F., Menc\u00eda, C., Ignatiev, A., Manthey, N., Pe\u00f1aloza, R., Marques-Silva, J.: BEACON: an efficient SAT-based tool for debugging $${\\cal{EL}}{^+}$$ ontologies. In: Creignou, N., Le Berre, D. (eds.) SAT 2016. LNCS, vol. 9710, pp. 521\u2013530. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-40970-2_32"},{"key":"19_CR2","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-319-24489-1_17","volume-title":"KI 2015: Advances in Artificial Intelligence","author":"MF Arif","year":"2015","unstructured":"Arif, M.F., Menc\u00eda, C., Marques-Silva, J.: Efficient axiom pinpointing with EL2MCS. In: H\u00f6lldobler, S., Kr\u00f6tzsch, M., Pe\u00f1aloza, R., Rudolph, S. (eds.) KI 2015. LNCS (LNAI), vol. 9324, pp. 225\u2013233. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-24489-1_17"},{"key":"19_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-319-24318-4_24","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2015","author":"MF Arif","year":"2015","unstructured":"Arif, M.F., Menc\u00eda, C., Marques-Silva, J.: Efficient MUS enumeration of horn formulae with applications to axiom pinpointing. In: Heule, M., Weaver, S. (eds.) SAT 2015. LNCS, vol. 9340, pp. 324\u2013342. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-24318-4_24"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.tcs.2016.03.016","volume":"658","author":"G Ausiello","year":"2017","unstructured":"Ausiello, G., Laura, L.: Directed hypergraphs: introduction and fundamental algorithms-a survey. Theor. Comput. Sci. 658, 293\u2013306 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: IJCAI, vol. 5, pp. 364\u2013369 (2005)","DOI":"10.25368\/2022.144"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-319-68288-4_11","volume-title":"The Semantic Web \u2013 ISWC 2017","author":"J Chen","year":"2017","unstructured":"Chen, J., Ludwig, M., Ma, Y., Walther, D.: Zooming in on ontologies: minimal modules and best excerpts. In: d\u2019Amato, C., et al. (eds.) ISWC 2017. LNCS, vol. 10587, pp. 173\u2013189. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68288-4_11"},{"issue":"2\u20133","key":"19_CR7","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G Gallo","year":"1993","unstructured":"Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discret. Appl. Math. 42(2\u20133), 177\u2013201 (1993)","journal-title":"Discret. Appl. Math."},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1613\/jair.2375","volume":"31","author":"BC Grau","year":"2008","unstructured":"Grau, B.C., Horrocks, I., Kazakov, Y., Sattler, U.: Modular reuse of ontologies: theory and practice. J. Artif. Intell. Res. 31, 273\u2013318 (2008)","journal-title":"J. Artif. Intell. Res."},{"key":"19_CR9","unstructured":"Ignatiev, A., Marques-Silva, J., Menc\u00eda, C., Pe\u00f1aloza, R.: Debugging EL+ ontologies through horn MUS enumeration. In: Artale, A., Glimm, B., Kontchakov, R. (eds.) Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, 18\u201321 July 2017. CEUR Workshop Proceedings, vol. 1879. CEUR-WS.org (2017). http:\/\/ceur-ws.org\/Vol-1879\/paper54.pdf"},{"key":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-540-76298-0_20","volume-title":"The Semantic Web","author":"A Kalyanpur","year":"2007","unstructured":"Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding all justifications of OWL DL entailments. In: Aberer, K., et al. (eds.) ASWC\/ISWC -2007. LNCS, vol. 4825, pp. 267\u2013280. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-76298-0_20"},{"issue":"4","key":"19_CR11","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.websem.2005.09.005","volume":"3","author":"A Kalyanpur","year":"2005","unstructured":"Kalyanpur, A., Parsia, B., Sirin, E., Hendler, J.: Debugging unsatisfiable classes in OWL ontologies. J. Web Semant. 3(4), 268\u2013293 (2005)","journal-title":"J. Web Semant."},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-319-11915-1_13","volume-title":"The Semantic Web \u2013 ISWC 2014","author":"Y Kazakov","year":"2014","unstructured":"Kazakov, Y., Klinov, P.: Goal-directed tracing of inferences in EL ontologies. In: Mika, P., et al. (eds.) ISWC 2014. LNCS, vol. 8797, pp. 196\u2013211. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11915-1_13"},{"key":"19_CR13","unstructured":"Kazakov, Y., Kr\u00f6tzsch, M., Simancik, F.: ELK reasoner: architecture and evaluation. In: ORE (2012)"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/978-3-319-94205-6_40","volume-title":"Automated Reasoning","author":"Y Kazakov","year":"2018","unstructured":"Kazakov, Y., Sko\u010dovsk\u00fd, P.: Enumerating justifications using resolution. In: Galmiche, D., Schulz, S., Sebastiani, R. (eds.) IJCAR 2018. LNCS (LNAI), vol. 10900, pp. 609\u2013626. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94205-6_40"},{"key":"19_CR15","doi-asserted-by":"publisher","unstructured":"Ludwig, M., Walther, D.: The logical difference for $$\\cal{ELH}$$$${}^{r}$$-terminologies using hypergraphs. In: Schaub, T., Friedrich, G., O\u2019Sullivan, B. (eds.) 21st European Conference on Artificial Intelligence, ECAI 2014, Prague, Czech Republic, 18\u201322 August 2014 - Including Prestigious Applications of Intelligent Systems (PAIS 2014). Frontiers in Artificial Intelligence and Applications, vol. 263, pp. 555\u2013560. IOS Press (2014). https:\/\/doi.org\/10.3233\/978-1-61499-419-0-555","DOI":"10.3233\/978-1-61499-419-0-555"},{"key":"19_CR16","unstructured":"Manthey, N., Pe\u00f1aloza, R., Rudolph, S.: Efficient axiom pinpointing in EL using sat technology. In: Description Logics (2016)"},{"key":"19_CR17","doi-asserted-by":"publisher","unstructured":"Pe\u00f1aloza, R.: Axiom pinpointing. In: Cota, G., Daquino, M., Pozzato, G.L. (eds.) Applications and Practices in Ontology Design, Extraction, and Reasoning, Studies on the Semantic Web, vol. 49, pp. 162\u2013177. IOS Press (2020). https:\/\/doi.org\/10.3233\/SSW200042","DOI":"10.3233\/SSW200042"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.artint.2017.06.002","volume":"250","author":"R Penaloza","year":"2017","unstructured":"Penaloza, R., Sertkaya, B.: Understanding the complexity of axiom pinpointing in lightweight description logics. Artif. Intell. 250, 80\u2013104 (2017)","journal-title":"Artif. Intell."}],"container-title":["Lecture Notes in Computer Science","Automated Reasoning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-10769-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T01:13:50Z","timestamp":1659316430000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-10769-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031107689","9783031107696"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-10769-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 August 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJCAR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Joint Conference on Automated Reasoning","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Haifa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Israel","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ijcar2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easychair.org\/smart-program\/FLoC2022\/IJCAR-index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}