{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:33:59Z","timestamp":1761806039782,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032095268","type":"print"},{"value":"9783032095275","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T00:00:00Z","timestamp":1761696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T00:00:00Z","timestamp":1761696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-09527-5_3","type":"book-chapter","created":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:30:19Z","timestamp":1761805819000},"page":"42-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["SAT-Based Bounded Fitting for\u00a0the\u00a0Description Logic $$\\mathcal {ALC}$$"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1823-9370","authenticated-orcid":false,"given":"Maurice","family":"Funk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4159-2255","authenticated-orcid":false,"given":"Jean Christoph","family":"Jung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-3149-7066","authenticated-orcid":false,"given":"Tom","family":"Voellmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,29]]},"reference":[{"key":"3_CR1","unstructured":"OWL 2 web ontology language overview. https:\/\/www.w3.org\/TR\/2012\/REC-owl2-overview-20121211\/. Accessed July 24 2025"},{"key":"3_CR2","unstructured":"Anthony, M., Biggs, N.: Computational Learning Theory: An Introduction. Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (1992)"},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An introduction to description logics. Cambridge University Press (2017). https:\/\/doi.org\/10.1017\/9781139025355","DOI":"10.1017\/9781139025355"},{"issue":"4","key":"3_CR4","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM (JACM) 36(4), 929\u2013965 (1989). https:\/\/doi.org\/10.1145\/76359.76371","journal-title":"J. ACM (JACM)"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Bordais, B., Neider, D., Roy, R.: The complexity of learning LTL, CTL and ATL formulas. In: Proceedings of 42nd International Symposium on Theoretical Aspects of Computer Science, STACS. LIPIcs, vol.\u00a0327, pp. 19:1\u201319:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2025.19","DOI":"10.4230\/LIPICS.STACS.2025.19"},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"B\u00fchmann, L., Lehmann, J., Westphal, P., Bin, S.: DL-Learner \u2013 structured machine learning on semantic web data. In: Companion Proceedings of the The Web Conference 2018. pp. 467\u2013471 (2018). https:\/\/doi.org\/10.1145\/3184558.3186235","DOI":"10.1145\/3184558.3186235"},{"key":"3_CR7","doi-asserted-by":"publisher","unstructured":"Camacho, A., McIlraith, S.A.: Learning interpretable models expressed in linear temporal logic. In: Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, ICAPS, pp. 621\u2013630. AAAI Press (2019). https:\/\/doi.org\/10.1609\/icaps.v29i1.3529","DOI":"10.1609\/icaps.v29i1.3529"},{"key":"3_CR8","doi-asserted-by":"publisher","unstructured":"ten Cate, B., Funk, M., Jung, J.C., Lutz, C.: Fitting algorithms for conjunctive queries. SIGMOD Rec. 52(4), 6\u201318 (2023). https:\/\/doi.org\/10.1145\/3641832.3641834","DOI":"10.1145\/3641832.3641834"},{"key":"3_CR9","doi-asserted-by":"publisher","unstructured":"ten Cate, B., Funk, M., Jung, J.C., Lutz, C.: SAT-based PAC learning of description logic concepts. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 3347\u20133355. ijcai.org (2023). https:\/\/doi.org\/10.24963\/IJCAI.2023\/373","DOI":"10.24963\/IJCAI.2023\/373"},{"key":"3_CR10","doi-asserted-by":"publisher","unstructured":"ten Cate, B., Funk, M., Jung, J.C., Lutz, C.: SAT-based PAC learning of description logic concepts. CoRR abs\/2305.08511 (2023). https:\/\/doi.org\/10.48550\/arXiv.2305.08511","DOI":"10.48550\/arXiv.2305.08511"},{"key":"3_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2023.106431","volume":"183","author":"B ten Cate","year":"2024","unstructured":"ten Cate, B., Funk, M., Jung, J.C., Lutz, C.: On the non-efficient PAC learnability of conjunctive queries. Inf. Process. Lett. 183, 106431 (2024). https:\/\/doi.org\/10.1016\/J.IPL.2023.106431","journal-title":"Inf. Process. Lett."},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Demir, C., Ngonga Ngomo, A.: Neuro-symbolic class expression learning. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pp. 3624\u20133632. ijcai.org (2023). https:\/\/doi.org\/10.24963\/ijcai.2023\/403","DOI":"10.24963\/ijcai.2023\/403"},{"key":"3_CR13","doi-asserted-by":"publisher","unstructured":"Funk, M., Jung, J.C., Lutz, C.: Actively learning concept and conjunctive queries under $$\\cal EL\\it ^r$$-ontologies. In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. pp. 1887\u20131893 (2021). https:\/\/doi.org\/10.24963\/ijcai.2021\/260","DOI":"10.24963\/ijcai.2021\/260"},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Funk, M., Jung, J.C., Lutz, C., Pulcini, H., Wolter, F.: Learning description logic concepts: When can positive and negative examples be separated? In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 1682\u20131688 (2019). https:\/\/doi.org\/10.24963\/ijcai.2019\/233","DOI":"10.24963\/ijcai.2019\/233"},{"key":"3_CR15","unstructured":"Funk, M., Jung, J.C., Voellmer, T.: SAT-based bounded fitting for the description logic $$\\cal{ALC}$$. CoRR arXiv:2507.21752 (2025), https:\/\/doi.org\/10.48550\/arXiv.2507.21752"},{"key":"3_CR16","doi-asserted-by":"publisher","unstructured":"Heindorf, S., et al.: EvoLearner: Learning description logics with evolutionary algorithms. In: WWW \u201922: The ACM Web Conference 2022, pp. 818\u2013828. ACM (2022). https:\/\/doi.org\/10.1145\/3485447.3511925","DOI":"10.1145\/3485447.3511925"},{"key":"3_CR17","unstructured":"Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible SROIQ. In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2-5, 2006, pp. 57\u201367. AAAI Press (2006), http:\/\/www.aaai.org\/Library\/KR\/2006\/kr06-009.php"},{"issue":"2","key":"3_CR18","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/S10489-006-0011-5","volume":"26","author":"L Iannone","year":"2007","unstructured":"Iannone, L., Palmisano, I., Fanizzi, N.: An algorithm based on counterfactuals for concept learning in the semantic web. Appl. Intell. 26(2), 139\u2013159 (2007). https:\/\/doi.org\/10.1007\/S10489-006-0011-5","journal-title":"Appl. Intell."},{"key":"3_CR19","doi-asserted-by":"publisher","unstructured":"Ignatiev, A., Morgado, A., Marques-Silva, J.: PySAT: A Python toolkit for prototyping with SAT oracles. In: Theory and Applications of Satisfiability Testing \u2013 SAT 2018, pp. 428\u2013437 (2018). https:\/\/doi.org\/10.1007\/978-3-319-94144-8_26","DOI":"10.1007\/978-3-319-94144-8_26"},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Ignatiev, A., Tan, Z.L., Karamanos, C.: Towards universally accessible SAT technology. In: 27th International Conference on Theory and Applications of Satisfiability Testing, pp. 4:1\u20134:11 (2024). https:\/\/doi.org\/10.4230\/LIPICS.SAT.2024.16","DOI":"10.4230\/LIPICS.SAT.2024.16"},{"issue":"1","key":"3_CR21","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"MJ Kearns","year":"1994","unstructured":"Kearns, M.J., Valiant, L.G.: Cryptographic limitations on learning Boolean formulae and finite automata. J. ACM (JACM) 41(1), 67\u201395 (1994). https:\/\/doi.org\/10.1145\/174644.174647","journal-title":"J. ACM (JACM)"},{"key":"3_CR22","doi-asserted-by":"publisher","unstructured":"Kietz, J.: Some lower bounds for the computational complexity of inductive logic programming. In: Machine Learning: ECML-93, pp. 115\u2013123 (1993). https:\/\/doi.org\/10.1007\/3-540-56602-3_131","DOI":"10.1007\/3-540-56602-3_131"},{"key":"3_CR23","doi-asserted-by":"publisher","unstructured":"Kouagou, N.J., Heindorf, S., Demir, C., Ngomo, A.N.: Neural class expression synthesis. In: The Semantic Web - 20th International Conference, ESWC 2023. Lecture Notes in Computer Science, vol. 13870, pp. 209\u2013226. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-33455-9_13","DOI":"10.1007\/978-3-031-33455-9_13"},{"key":"3_CR24","doi-asserted-by":"publisher","unstructured":"Kouagou, N.J., Heindorf, S., Demir, C., Ngonga Ngomo, A.: Neural class expression synthesis in ALCHIQ(D). In: Machine Learning and Knowledge Discovery in Databases: Research Track - European Conference, ECML PKDD 2023. Lecture Notes in Computer Science, vol. 14172, pp. 196\u2013212. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-43421-1_12","DOI":"10.1007\/978-3-031-43421-1_12"},{"key":"3_CR25","doi-asserted-by":"publisher","unstructured":"Lehmann, J.: Learning OWL Class Expressions, Studies on the Semantic Web, vol.\u00a06. IOS Press (2010). https:\/\/doi.org\/10.3233\/978-1-61499-340-7-i","DOI":"10.3233\/978-1-61499-340-7-i"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Lehmann, J., Fanizzi, N., B\u00fchmann, L., d\u2019Amato, C.: Concept learning. In: Perspectives on Ontology Learning, pp. 71\u201391. AKA \/ IOS Press (2014), https:\/\/jens-lehmann.org\/files\/2014\/pol_concept_learning.pdf","DOI":"10.3233\/978-1-61499-379-7-i"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s10994-009-5146-2","volume":"78","author":"J Lehmann","year":"2010","unstructured":"Lehmann, J., Hitzler, P.: Concept learning in description logics using refinement operators. Mach. Learn. 78, 203\u2013250 (2010). https:\/\/doi.org\/10.1007\/s10994-009-5146-2","journal-title":"Mach. Learn."},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/J.IS.2019.03.002","volume":"83","author":"DML Martins","year":"2019","unstructured":"Martins, D.M.L.: Reverse engineering database queries from examples: State-of-the-art, challenges, and research opportunities. Inf. Syst. 83, 89\u2013100 (2019). https:\/\/doi.org\/10.1016\/J.IS.2019.03.002","journal-title":"Inf. Syst."},{"key":"3_CR29","doi-asserted-by":"publisher","unstructured":"Mascle, C., Fijalkow, N., Lagarde, G.: Learning temporal formulas from examples is hard. CoRR abs\/2312.16336 (2023). https:\/\/doi.org\/10.48550\/ARXIV.2312.16336","DOI":"10.48550\/ARXIV.2312.16336"},{"key":"3_CR30","doi-asserted-by":"publisher","unstructured":"Neider, D., Gavran, I.: Learning linear temporal properties. In: Proceedings of 18th Conference on Formal Methods in Computer Aided Design FMCAD, pp. 1\u201310. IEEE (2018). https:\/\/doi.org\/10.23919\/FMCAD.2018.8603016","DOI":"10.23919\/FMCAD.2018.8603016"},{"issue":"4","key":"3_CR31","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L Pitt","year":"1988","unstructured":"Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965\u2013984 (1988). https:\/\/doi.org\/10.1145\/48014.63140","journal-title":"J. ACM"},{"key":"3_CR32","doi-asserted-by":"publisher","unstructured":"Pommellet, A., Stan, D., Scatton, S.: SAT-based learning of computation tree logic. In: Proceedings of 12th International Joint Conference on Automated Reasoning IJCAR. Lecture Notes in Computer Science, vol. 14739, pp. 366\u2013385. Springer (2024). https:\/\/doi.org\/10.1007\/978-3-031-63498-7_22","DOI":"10.1007\/978-3-031-63498-7_22"},{"key":"3_CR33","doi-asserted-by":"publisher","unstructured":"Riener, H.: Exact synthesis of LTL properties from traces. In: Kazmierski, T.J., von Hanxleden, R., Mak, T.S.T. (eds.) 2019 Forum for Specification and Design Languages, FDL 2019, Southampton, United Kingdom, September 2-4, 2019, pp.\u00a01\u20136. IEEE (2019). https:\/\/doi.org\/10.1109\/FDL.2019.8876900","DOI":"10.1109\/FDL.2019.8876900"},{"key":"3_CR34","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/J.FUTURE.2020.02.071","volume":"108","author":"G Rizzo","year":"2020","unstructured":"Rizzo, G., Fanizzi, N., d\u2019Amato, C.: Class expression induction as concept space exploration: from DL-FOIL to DL-FOCL. Future Gener. Comput. Syst. 108, 256\u2013272 (2020). https:\/\/doi.org\/10.1016\/J.FUTURE.2020.02.071","journal-title":"Future Gener. Comput. Syst."},{"key":"3_CR35","doi-asserted-by":"publisher","unstructured":"Sakallah, K.A.: Symmetry and satisfiability. In: Handbook of Satisfiability - Second Edition, Frontiers in Artificial Intelligence and Applications, vol.\u00a0336, pp. 509\u2013570. IOS Press (2021). https:\/\/doi.org\/10.3233\/FAIA200996","DOI":"10.3233\/FAIA200996"},{"key":"3_CR36","doi-asserted-by":"publisher","unstructured":"Suchanek, F.M., Alam, M., Bonald, T., Chen, L., Paris, P., Soria, J.: YAGO 4.5: A large and clean knowledge base with a rich taxonomy. In: Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2024, pp. 131\u2013140. ACM (2024). https:\/\/doi.org\/10.1145\/3626772.3657876","DOI":"10.1145\/3626772.3657876"},{"key":"3_CR37","unstructured":"Tran, A.C., Dietrich, J., Guesgen, H.W., Marsland, S.: Parallel symmetric class expression learning. J. Mach. Learn. Res. 18, 64:1\u201364:34 (2017). https:\/\/jmlr.org\/papers\/v18\/14-317.html"},{"issue":"11","key":"3_CR38","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984). https:\/\/doi.org\/10.1145\/1968.1972","journal-title":"Commun. ACM"},{"issue":"2","key":"3_CR39","doi-asserted-by":"publisher","first-page":"231","DOI":"10.3233\/SW-180308","volume":"10","author":"P Westphal","year":"2019","unstructured":"Westphal, P., B\u00fchmann, L., Bin, S., Jabeen, H., Lehmann, J.: SML-bench - a benchmarking framework for structured machine learning. Semantic Web 10(2), 231\u2013245 (2019). https:\/\/doi.org\/10.3233\/SW-180308","journal-title":"Semantic Web"},{"key":"3_CR40","doi-asserted-by":"publisher","unstructured":"Zloof, M.M.: Query by example. In: American Federation of Information Processing Societies: 1975 National Computer Conference, 19-22 May 1975, Anaheim, CA, USA. AFIPS Conference Proceedings, vol.\u00a044, pp. 431\u2013438. AFIPS Press (1975). https:\/\/doi.org\/10.1145\/1499949.1500034","DOI":"10.1145\/1499949.1500034"}],"container-title":["Lecture Notes in Computer Science","The Semantic Web \u2013 ISWC 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-09527-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:30:41Z","timestamp":1761805841000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-09527-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,29]]},"ISBN":["9783032095268","9783032095275"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-09527-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,29]]},"assertion":[{"value":"29 October 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"The source code of our implementation ALC-SAT\n                      \n                      and instructions on how to reproduce the benchmarks are available at\n                      \n                      . The full version of this paper including all proof details is available under\u00a0[\n                      \n                      ].","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Supplemental Material Statement"}},{"value":"ISWC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Semantic Web Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nara","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 November 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 November 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"semweb2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iswc2025.semanticweb.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}