{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:54:00Z","timestamp":1757624040870,"version":"3.44.0"},"reference-count":65,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T00:00:00Z","timestamp":1754956800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T00:00:00Z","timestamp":1754956800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007241","name":"Universit\u00e9 Paris-Saclay","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007241","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Neurosymbolic artificial intelligence is a growing field of research aiming to combine neural network learning capabilities with the reasoning abilities of symbolic systems. Informed multi-label classification is a sub-field of neurosymbolic AI which studies how to leverage prior knowledge to improve neural classification systems. Recently, a family of neurosymbolic techniques for informed classification based on probabilistic reasoning has gained significant traction. Unfortunately, depending on the language used to represent prior knowledge, solving certain probabilistic reasoning problems can become prohibitively hard when the number of classes increases. Therefore, the asymptotic complexity of probabilistic reasoning is of cardinal importance to assess the scalability of such techniques. In this paper, we develop a unified formalism for four probabilistic reasoning problems. Then, we compile several known and new tractability results into a single complexity map of probabilistic reasoning. We build on top of this complexity map to characterize the domains of scalability of several techniques. We hope this work will help neurosymbolic AI practitioners navigate the scalability landscape of probabilistic neurosymbolic techniques.<\/jats:p>","DOI":"10.1007\/s11786-025-00603-7","type":"journal-article","created":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T04:34:32Z","timestamp":1754973272000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Complexity Map of Probabilistic Reasoning for Neurosymbolic Classification Techniques"],"prefix":"10.1007","volume":"19","author":[{"given":"Arthur","family":"Ledaguenel","sequence":"first","affiliation":[]},{"given":"C\u00e9line","family":"Hudelot","sequence":"additional","affiliation":[]},{"given":"Mostepha","family":"Khouadjia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,12]]},"reference":[{"key":"603_CR1","first-page":"93","volume":"43","author":"HA Kautz","year":"2022","unstructured":"Kautz, H.A.: The third AI summer: AAAI Robert S. Engelmore memorial lecture. AI Mag. 43, 93\u2013104 (2022)","journal-title":"AI Mag."},{"key":"603_CR2","unstructured":"Wang, W., Yang, Y., Wu, F.: Towards data-and knowledge-driven artificial intelligence: a survey on neuro-symbolic computing (2023). https:\/\/arxiv.org\/abs\/2210.15889"},{"issue":"1","key":"603_CR3","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1109\/TKDE.2021.3079836","volume":"35","author":"L Rueden","year":"2023","unstructured":"Rueden, L., Mayer, S., Beckh, K., Georgiev, B., Giesselbach, S., Heese, R., Kirsch, B., Pfrommer, J., Pick, A., Ramamurthy, R., Walczak, M., Garcke, J., Bauckhage, C., Schuecker, J.: Informed machine learning\u2014a taxonomy and survey of integrating prior knowledge into learning systems. IEEE Trans. Knowl. Data Eng. 35(1), 614\u2013633 (2023). https:\/\/doi.org\/10.1109\/TKDE.2021.3079836","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"603_CR4","doi-asserted-by":"crossref","unstructured":"Deng, J., Ding, N., Jia, Y., Frome, A., Murphy, K., Bengio, S., Li, Y., Neven, H., Adam, H.: Large-scale object classification using label relation graphs. In: Computer Vision\u2014ECCV 2014, pp. 48\u201364 (2014)","DOI":"10.1007\/978-3-319-10590-1_4"},{"key":"603_CR5","unstructured":"Xu, J., Zhang, Z., Friedman, T., Liang, Y., Broeck, G.: A semantic loss function for deep learning with symbolic knowledge. In: Dy, J., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 80, pp. 5502\u20135511 (2018). https:\/\/proceedings.mlr.press\/v80\/xu18h.html"},{"key":"603_CR6","doi-asserted-by":"publisher","unstructured":"Yang, Z., Ishay, A., Lee, J.: NeurASP: embracing neural networks into answer set programming. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pp. 1755\u20131762. International Joint Conferences on Artificial Intelligence Organization. https:\/\/doi.org\/10.24963\/ijcai.2020\/243","DOI":"10.24963\/ijcai.2020\/243"},{"key":"603_CR7","doi-asserted-by":"publisher","first-page":"103504","DOI":"10.1016\/j.artint.2021.103504","volume":"298","author":"R Manhaeve","year":"2021","unstructured":"Manhaeve, R., Duman\u010di\u0107, S., Kimmig, A., Demeester, T., De Raedt, L.: Neural probabilistic logic programming in DeepProbLog. Artif. Intell. 298, 103504 (2021). https:\/\/doi.org\/10.1016\/j.artint.2021.103504","journal-title":"Artif. Intell."},{"key":"603_CR8","unstructured":"Ahmed, K., Teso, S., Chang, K.-W., Broeck, G., Vergari, A.: Semantic probabilistic layers for neuro-symbolic learning. In: Advances in Neural Information Processing Systems, vol. 35, pp. 29944\u201329959 (2022)"},{"key":"603_CR9","doi-asserted-by":"crossref","unstructured":"Ahmed, K., Wang, E., Chang, K.-W., Broeck, G.: Neuro-symbolic entropy regularization. In: Cussens, J., Zhang, K. (eds.) Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence. Proceedings of Machine Learning Research, vol. 180, pp. 43\u201353 (2022). https:\/\/proceedings.mlr.press\/v180\/ahmed22a.html","DOI":"10.1201\/9781003055129-3"},{"key":"603_CR10","doi-asserted-by":"publisher","unstructured":"Suciu, D.: Probabilistic databases for all. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems, pp. 19\u201331 (2020). https:\/\/doi.org\/10.1145\/3375395.3389129","DOI":"10.1145\/3375395.3389129"},{"issue":"9","key":"603_CR11","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1016\/j.ijar.2011.08.003","volume":"52","author":"J Kwisthout","year":"2011","unstructured":"Kwisthout, J.: Most probable explanations in Bayesian networks: complexity and tractability. Int. J. Approx. Reason. 52(9), 1452\u20131469 (2011)","journal-title":"Int. J. Approx. Reason."},{"key":"603_CR12","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s11263-015-0816-y","volume":"115","author":"O Russakovsky","year":"2015","unstructured":"Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A.C., Fei-Fei, L.: Imagenet large scale visual recognition challenge. Int. J. Comput. Vis. 115, 211\u2013252 (2015). https:\/\/doi.org\/10.1007\/s11263-015-0816-y","journal-title":"Int. J. Comput. Vis."},{"key":"603_CR13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/219717.219748","volume":"38","author":"GA Miller","year":"1995","unstructured":"Miller, G.A.: Wordnet. Commun. ACM 38, 39\u201341 (1995). https:\/\/doi.org\/10.1145\/219717.219748","journal-title":"Commun. ACM"},{"key":"603_CR14","doi-asserted-by":"publisher","unstructured":"Gebru, T., Krause, J., Wang, Y., Chen, D., Deng, J., Fei-Fei, L.: Fine-grained car detection for visual census estimation, vol. 31, no. 1. https:\/\/doi.org\/10.1609\/aaai.v31i1.11174. Number: 1. Accessed 31 Mar 2024","DOI":"10.1609\/aaai.v31i1.11174"},{"key":"603_CR15","doi-asserted-by":"publisher","unstructured":"Van\u00a0Horn, G., Mac\u00a0Aodha, O., Song, Y., Cui, Y., Sun, C., Shepard, A., Adam, H., Perona, P., Belongie, S.: The inaturalist species classification and detection dataset. In: 2018 IEEE\/CVF Conference on Computer Vision and Pattern Recognition, pp. 8769\u20138778 (2018). https:\/\/doi.org\/10.1109\/CVPR.2018.00914","DOI":"10.1109\/CVPR.2018.00914"},{"key":"603_CR16","doi-asserted-by":"publisher","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Y LeCun","year":"1998","unstructured":"LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86, 2278\u20132323 (1998). https:\/\/doi.org\/10.1109\/5.726791","journal-title":"Proc. IEEE"},{"key":"603_CR17","unstructured":"Xiao, H., Rasul, K., Vollgraf, R.: Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms (2017). https:\/\/arxiv.org\/abs\/1708.07747"},{"key":"603_CR18","unstructured":"Krizhevsky, A.: Learning multiple layers of features from tiny images (2009)"},{"key":"603_CR19","unstructured":"Krieken, E., Thanapalasingam, T., Tomczak, J.M., Harmelen, F., Teije, A.: A-NeSI: a scalable approximate method for probabilistic neurosymbolic inference (2022)"},{"key":"603_CR20","unstructured":"Maene, J., De\u00a0Raedt, L.: Soft-unification in deep probabilistic logic, vol. 36. Accessed 21 Feb 2024"},{"issue":"1","key":"603_CR21","first-page":"229","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Sci. 17(1), 229\u2013264 (2002)","journal-title":"J. Artif. Intell. Sci."},{"issue":"1","key":"603_CR22","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1010933404324","volume":"45","author":"L Breiman","year":"2001","unstructured":"Breiman, L.: Random forests. Mach. Learn. 45(1), 5\u201332 (2001). https:\/\/doi.org\/10.1023\/A:1010933404324","journal-title":"Mach. Learn."},{"key":"603_CR23","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/3-540-59119-2_166","volume-title":"Computational Learning Theory","author":"Y Freund","year":"1995","unstructured":"Freund, Y., Schapire, R.E.: A desicion-theoretic generalization of on-line learning and an application to boosting. In: Vit\u00e1nyi, P. (ed.) Computational Learning Theory, pp. 23\u201337. Springer, Cham (1995). https:\/\/doi.org\/10.1007\/3-540-59119-2_166"},{"key":"603_CR24","unstructured":"Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., Bengio, Y.: Binarized neural networks. In: Advances in Neural Information Processing Systems, vol. 29. Curran Associates, Inc. https:\/\/papers.nips.cc\/paper_files\/paper\/2016\/hash\/d8330f857a17c53d217014ee776bfd50-Abstract.html Accessed 2024-04-22"},{"key":"603_CR25","unstructured":"Brewka, G., Eiter, T.: Equilibria in heterogeneous nonmonotonic multi-context systems. In: AAAI Conference on Artificial Intelligence (2007). https:\/\/api.semanticscholar.org\/CorpusID:224642"},{"issue":"2","key":"603_CR26","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10472-023-09914-6","volume":"92","author":"Y Lierler","year":"2024","unstructured":"Lierler, Y.: An abstract view on optimizations in propositional frameworks. Ann. Math. Artif. Intell. 92(2), 355\u2013391 (2024). https:\/\/doi.org\/10.1007\/s10472-023-09914-6","journal-title":"Ann. Math. Artif. Intell."},{"key":"603_CR27","unstructured":"Russell, S., Norvig, P.: Artificial Intelligence A Modern Approach (4th Edition), pp. 208\u2013250 (2021). Chap. 7"},{"issue":"8","key":"603_CR28","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"C\u201335","author":"RE Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C\u201335(8), 677\u2013691 (1986). https:\/\/doi.org\/10.1109\/TC.1986.1676819","journal-title":"IEEE Trans. Comput."},{"key":"603_CR29","unstructured":"Amarilli, A., Arenas, M., Choi, Y., Monet, M., Broeck, G., Wang, B.: A circus of circuits: connections between decision diagrams, circuits, and automata. arXiv preprint arXiv:2404.09674 (2024)"},{"key":"603_CR30","unstructured":"Darwiche, A.: SDD: a new canonical representation of propositional knowledge bases. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (2011)"},{"key":"603_CR31","doi-asserted-by":"crossref","unstructured":"Le\u00a0Berre, D., Marquis, P., Mengel, S., Wallon, R.: Pseudo-Boolean constraints from a knowledge representation perspective. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI\u201918, pp. 1891\u20131897. AAAI Press","DOI":"10.24963\/ijcai.2018\/261"},{"key":"603_CR32","doi-asserted-by":"publisher","unstructured":"Li, C.M., Many & #224, Felip: Chapter 23. MaxSAT, hard and soft constraints. In: Handbook of Satisfiability, pp. 903\u2013927. IOS Press. https:\/\/doi.org\/10.3233\/FAIA201007. https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA201007. Accessed 13 Nov 2024","DOI":"10.3233\/FAIA201007"},{"key":"603_CR33","unstructured":"Niepert, M., Minervini, P., Franceschi, L.: Implicit MLE: backpropagating through discrete exponential family distributions. In: Advances in Neural Information Processing Systems, vol. 34, pp. 14567\u201314579 (2021). https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/hash\/7a430339c10c642c4b2251756fd1b484-Abstract.html. Accessed 17 Jan 2024"},{"key":"603_CR34","unstructured":"Ledaguenel, A., Hudelot, C., Khouadjia, M.: Neurosymbolic conformal classification (2024). arXiv preprint arXiv:2409.13585"},{"key":"603_CR35","unstructured":"Ledaguenel, A., Hudelot, C., Khouadjia, M.: Improving neural-based classification with logical background knowledge (2024). https:\/\/arxiv.org\/abs\/2402.13019"},{"key":"603_CR36","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.artint.2015.08.011","volume":"244","author":"M Diligenti","year":"2017","unstructured":"Diligenti, M., Gori, M., Sacc\u00e0, C.: Semantic-based regularization for learning and inference. Artif. Intell. 244, 143\u2013165 (2017). https:\/\/doi.org\/10.1016\/j.artint.2015.08.011","journal-title":"Artif. Intell."},{"issue":"15","key":"603_CR37","doi-asserted-by":"publisher","first-page":"18775","DOI":"10.1007\/s10489-022-04383-6","volume":"53","author":"F Giannini","year":"2023","unstructured":"Giannini, F., Diligenti, M., Maggini, M., Gori, M., Marra, G.: T-norms driven loss functions for machine learning. Appl. Intell. 53(15), 18775\u201318789 (2023). https:\/\/doi.org\/10.1007\/s10489-022-04383-6","journal-title":"Appl. Intell."},{"key":"603_CR38","doi-asserted-by":"publisher","first-page":"103649","DOI":"10.1016\/j.artint.2021.103649","volume":"303","author":"S Badreddine","year":"2022","unstructured":"Badreddine, S., Garcez, A., Serafini, L., Spranger, M.: Logic tensor networks. Artif. Intell. 303, 103649 (2022). https:\/\/doi.org\/10.1016\/j.artint.2021.103649","journal-title":"Artif. Intell."},{"key":"603_CR39","unstructured":"Grandvalet, Y., Bengio, Y.: Semi-supervised learning by entropy minimization. In: Proceedings of the 17th International Conference on Neural Information Processing Systems. NIPS\u201904, pp. 529\u2013536. MIT Press, Cambridge, MA, USA (2004)"},{"key":"603_CR40","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-319-17091-6_19","volume-title":"Statistical Learning and Data Sciences","author":"H Wang","year":"2015","unstructured":"Wang, H., Liu, X., Nouretdinov, I., Luo, Z.: A comparison of three implementations of multi-label conformal prediction. In: Gammerman, A., Vovk, V., Papadopoulos, H. (eds.) Statistical Learning and Data Sciences, pp. 241\u2013250. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-17091-6_19"},{"key":"603_CR41","unstructured":"Bourhis, P., Duchien, L., Dusart, J., Lonca, E., Marquis, P., Quinton, C.: Pseudo polynomial-time top-k algorithms for d-DNNF circuits (2022). https:\/\/arxiv.org\/abs\/2202.05938"},{"key":"603_CR42","doi-asserted-by":"publisher","unstructured":"Kiesel, R., Eiter, T.: Knowledge compilation and more with SharpSAT-TD. In: Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, pp. 406\u2013416 (2023).https:\/\/doi.org\/10.24963\/kr.2023\/40","DOI":"10.24963\/kr.2023\/40"},{"key":"603_CR43","unstructured":"Darwiche, A.: New advances in compiling CNF to decomposable negation normal form. In: Proceedings of the 16th European Conference on Artificial Intelligence. ECAI\u201904, pp. 318\u2013322, NLD (2004)"},{"key":"603_CR44","doi-asserted-by":"crossref","unstructured":"Muise, C., McIlraith, S.A., Beck, J.C., Hsu, E.I.: DSHARP: Fast d-DNNF compilation with sharpSAT. In: Kosseim, L., Inkpen, D. (eds.) Advances in Artificial Intelligence, pp. 356\u2013361, Berlin, Heidelberg (2012)","DOI":"10.1007\/978-3-642-30353-1_36"},{"key":"603_CR45","doi-asserted-by":"publisher","unstructured":"Lagniez, J.-M., Marquis, P.: An improved decision-DNNF compiler. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 667\u2013673 (2017). https:\/\/doi.org\/10.24963\/ijcai.2017\/93","DOI":"10.24963\/ijcai.2017\/93"},{"issue":"5","key":"603_CR46","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991). https:\/\/doi.org\/10.1137\/0220053","journal-title":"SIAM J. Comput."},{"issue":"11","key":"603_CR47","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1287\/mnsc.22.11.1268","volume":"22","author":"J-C Picard","year":"1976","unstructured":"Picard, J.-C.: Maximal closure of a graph and applications to combinatorial problems. Manag. Sci. 22(11), 1268\u20131272 (1976). https:\/\/doi.org\/10.1287\/mnsc.22.11.1268","journal-title":"Manag. Sci."},{"issue":"6","key":"603_CR48","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0167-6377(84)90083-X","volume":"2","author":"HW Hamacher","year":"1984","unstructured":"Hamacher, H.W., Picard, J.-C., Queyranne, M.: On finding the k best cuts in a network. Oper. Res. Lett. 2(6), 303\u2013305 (1984). https:\/\/doi.org\/10.1016\/0167-6377(84)90083-X","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"603_CR49","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"JS Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12(4), 777\u2013788 (1983). https:\/\/doi.org\/10.1137\/0212053","journal-title":"SIAM J. Comput."},{"key":"603_CR50","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and Sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department. The IBM Research Symposia Series, pp. 85\u2013103. Springer. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9. Accessed 11 Mar 2024","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"603_CR51","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979). https:\/\/doi.org\/10.1137\/0208032","journal-title":"SIAM J. Comput."},{"key":"603_CR52","unstructured":"Pogan\u010di\u0107, M.V., Paulus, A., Musil, V., Martius, G., Rolinek, M.: Differentiation of blackbox combinatorial solvers (2019). https:\/\/openreview.net\/forum?id=BkevoJSYPB. Accessed 27 Oct 2023"},{"key":"603_CR53","unstructured":"Ahmed, K., Zeng, Z., Niepert, M., Broeck, G.: Simple: a gradient estimator for k-subset sampling. In: Proceedings of the international conference on learning representations (ICLR) (2023). http:\/\/starai.cs.ucla.edu\/papers\/AhmedICLR23.pdf"},{"key":"603_CR54","doi-asserted-by":"publisher","unstructured":"Ling, J., Chandak, K., Kumar, A.: Integrating knowledge compilation with reinforcement learning for routes. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 31, pp. 542\u2013550. https:\/\/doi.org\/10.1609\/icaps.v31i1.16002. ISSN: 2334-0843, 2334-0835 Journal Abbreviation: ICAPS. https:\/\/ojs.aaai.org\/index.php\/ICAPS\/article\/view\/16002. Accessed 14 Nov 2024","DOI":"10.1609\/icaps.v31i1.16002"},{"key":"603_CR55","unstructured":"Nishino, M., Yasuda, N., Minato, S.-i., Nagata, M.: Compiling graph substructures into sentential decision diagrams. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. AAAI\u201917, pp. 1213\u20131221. AAAI Press"},{"key":"603_CR56","unstructured":"Choi, A., Shen, Y., Darwiche, A.: Tractability in structured probability spaces. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. NIPS\u201917, pp. 3480\u20133488. Curran Associates Inc"},{"key":"603_CR57","doi-asserted-by":"publisher","unstructured":"Shen, Y., Goyanka, A., Darwiche, A., Choi, A.: Structured Bayesian networks: from inference to learning with routes, vol. 33, no. 1, pp. 7957\u20137965. https:\/\/doi.org\/10.1609\/aaai.v33i01.33017957. Number: 01. Accessed 14 Nov 2024","DOI":"10.1609\/aaai.v33i01.33017957"},{"key":"603_CR58","unstructured":"Ahmed, K., Chang, K.-W., Broeck, G.: Semantic strengthening of neuro-symbolic learning. In: Ruiz, F., Dy, J., Meent, J.-W. (eds.) Proceedings of the 26th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 206, pp. 10252\u201310261 (2023). https:\/\/proceedings.mlr.press\/v206\/ahmed23a.html"},{"key":"603_CR59","doi-asserted-by":"publisher","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices, vol. 69B, no. 1. https:\/\/doi.org\/10.6028\/jres.069b.013. Number: 1 and 2. Accessed 11 Mar 2024","DOI":"10.6028\/jres.069b.013"},{"issue":"2","key":"603_CR60","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0166-218X(87)90017-5","volume":"18","author":"CR Chegireddy","year":"1987","unstructured":"Chegireddy, C.R., Hamacher, H.W.: Algorithms for finding k-best perfect matchings. Discret. Appl. Math. 18(2), 155\u2013165 (1987). https:\/\/doi.org\/10.1016\/0166-218X(87)90017-5","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"603_CR61","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1007\/s00224-019-09930-2","volume":"64","author":"A Amarilli","year":"2020","unstructured":"Amarilli, A., Capelli, F., Monet, M., Senellart, P.: Connecting knowledge compilation classes width parameters. Theory Comput. Syst. 64(5), 861\u2013914 (2020). https:\/\/doi.org\/10.1007\/s00224-019-09930-2","journal-title":"Theory Comput. Syst."},{"key":"603_CR62","doi-asserted-by":"publisher","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer. https:\/\/doi.org\/10.1007\/978-3-662-53622-3. https:\/\/link.springer.com\/10.1007\/978-3-662-53622-3. Accessed 29 Oct 2024","DOI":"10.1007\/978-3-662-53622-3"},{"key":"603_CR63","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198522195.001.0001","volume-title":"Graphical Models","author":"SL Lauritzen","year":"1996","unstructured":"Lauritzen, S.L.: Graphical Models. Clarendon Press, Oxford (1996)"},{"issue":"2","key":"603_CR64","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"FR Kschischang","year":"2002","unstructured":"Kschischang, F.R., Frey, B.J., Loeliger, H.A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47(2), 498\u2013519 (2002). https:\/\/doi.org\/10.1109\/18.910572","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"603_CR65","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/inco.2001.3043","volume":"176","author":"M Cadoli","year":"2002","unstructured":"Cadoli, M., Donini, F.M., Liberatore, P., Schaerf, M.: Preprocessing of intractable problems. Inf. Comput. 176(2), 89\u2013120 (2002). https:\/\/doi.org\/10.1006\/inco.2001.3043","journal-title":"Inf. Comput."}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-025-00603-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11786-025-00603-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-025-00603-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T10:38:53Z","timestamp":1757414333000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11786-025-00603-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,12]]},"references-count":65,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["603"],"URL":"https:\/\/doi.org\/10.1007\/s11786-025-00603-7","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"type":"print","value":"1661-8270"},{"type":"electronic","value":"1661-8289"}],"subject":[],"published":{"date-parts":[[2025,8,12]]},"assertion":[{"value":"29 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"8"}}