{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T02:35:06Z","timestamp":1783564506135,"version":"3.55.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>In this paper, we investigate the computational intelligibility of Boolean classifiers,\n\n        characterized by their ability to answer XAI queries in polynomial time.\n\n        The classifiers under consideration are decision trees, DNF formulae, decision lists, decision rules, tree ensembles, and\n\n        Boolean neural nets. Using 9 XAI queries, including both explanation queries and verification queries,\n\n        we show the existence of large intelligibility gap between the families of classifiers. On the one hand, all the 9 XAI queries\n\n        are tractable for decision trees. On the other hand, none of them is tractable for DNF formulae, decision lists, random forests, boosted decision trees,\n\n        Boolean multilayer perceptrons, and binarized neural networks.<\/jats:p>","DOI":"10.24963\/kr.2021\/8","type":"proceedings-article","created":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T16:45:56Z","timestamp":1633970756000},"page":"74-86","source":"Crossref","is-referenced-by-count":17,"title":["On the Computational Intelligibility of Boolean Classifiers"],"prefix":"10.24963","author":[{"given":"Gilles","family":"Audemard","sequence":"first","affiliation":[{"name":"CRIL, Universit\u00e9 d'Artois & CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steve","family":"Bellart","sequence":"additional","affiliation":[{"name":"CRIL, Universit\u00e9 d'Artois & CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Louenas","family":"Bounia","sequence":"additional","affiliation":[{"name":"CRIL, Universit\u00e9 d'Artois & CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Koriche","sequence":"additional","affiliation":[{"name":"CRIL, Universit\u00e9 d'Artois & CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Marie","family":"Lagniez","sequence":"additional","affiliation":[{"name":"CRIL, Universit\u00e9 d'Artois & CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Marquis","sequence":"additional","affiliation":[{"name":"CRIL, Universit\u00e9 d'Artois & CNRS"},{"name":"Institut Universitaire de France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"18th International Conference on Principles of Knowledge Representation and Reasoning {KR-2021}","theme":"Artificial Intelligence","location":"Hanoii, Vietnam","acronym":"KR-2021","number":"18","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Sea AI Lab","Potassco Solutions","European Association for Artificial Intelligence"],"start":{"date-parts":[[2020,11,12]]},"end":{"date-parts":[[2021,11,18]]}},"container-title":["Proceedings of the Eighteenth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T16:46:01Z","timestamp":1633970761000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2021\/8"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2021\/8","relation":{},"subject":[],"published":{"date-parts":[[2021,9]]}}}