{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:18:58Z","timestamp":1672291138709},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>Abduction is one of the most important forms of reasoning; it has been successfully applied to several practical problems, such as diagnosis. In this article we investigate whether the computational complexity of abduction can be reduced by an appropriate use of preprocessing. This is motivated by the fact that part of the data of the problem (namely, the set of all possible assumptions and the theory relating assumptions and manifestations) is often known before the rest of the problem. In this article, we show some complexity results about abduction when compilation is allowed.<\/jats:p>","DOI":"10.1145\/1182613.1182615","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"2","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Compilability of propositional abduction"],"prefix":"10.1145","volume":"8","author":[{"given":"Paolo","family":"Liberatore","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Schaerf","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,1]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 1st International Conference on the Principles of Knowledge Representation and Reasoning (KR). 44--54","author":"Bylander T.","unstructured":"Bylander , T. , Allemang , D. , Tanner , M. C. , and Josephson , J. R . 1989. Some results concerning the computational complexity of abduction . In Proceedings of the 1st International Conference on the Principles of Knowledge Representation and Reasoning (KR). 44--54 . Bylander, T., Allemang, D., Tanner, M. C., and Josephson, J. R. 1989. Some results concerning the computational complexity of abduction. In Proceedings of the 1st International Conference on the Principles of Knowledge Representation and Reasoning (KR). 44--54."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90005-5"},{"key":"e_1_2_1_3_1","first-page":"137","article-title":"A survey on knowledge compilation","volume":"10","author":"Cadoli M.","year":"1997","unstructured":"Cadoli , M. and Donini , F. M. 1997 . A survey on knowledge compilation . AI Commun. European J. Artif. Intell. 10 , 137 -- 150 . Cadoli, M. and Donini, F. M. 1997. A survey on knowledge compilation. AI Commun. European J. Artif. Intell. 10, 137--150.","journal-title":"AI Commun. European J. Artif. Intell."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622262.1622263"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3043"},{"key":"e_1_2_1_6_1","first-page":"86","article-title":"Abduction is not deduction-in-reverse","volume":"4","author":"Cialdea Mayer M.","year":"1996","unstructured":"Cialdea Mayer , M. and Pirri , F. 1996 . Abduction is not deduction-in-reverse . J. IGPL 4 , 1, 86 -- 104 . Cialdea Mayer, M. and Pirri, F. 1996. Abduction is not deduction-in-reverse. J. IGPL 4, 1, 86--104.","journal-title":"J. IGPL"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.542024"},{"key":"e_1_2_1_8_1","first-page":"229","article-title":"A knowledge compilation map","volume":"17","author":"Darwiche A.","year":"2002","unstructured":"Darwiche , A. and Marquis , P. 2002 . A knowledge compilation map . J. Automat. Reasoning 17 , 229 -- 264 . Darwiche, A. and Marquis, P. 2002. A knowledge compilation map. J. Automat. Reasoning 17, 229--264.","journal-title":"J. Automat. Reasoning"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90080-9"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 16th National Conference on Artificial Intelligence (AAAI). 259--264","author":"Del Val A.","year":"1999","unstructured":"Del Val , A. 1999 . A new method for consequence finding and compilation in restricted languages . In Proceedings of the 16th National Conference on Artificial Intelligence (AAAI). 259--264 . Del Val, A. 1999. A new method for consequence finding and compilation in restricted languages. In Proceedings of the 16th National Conference on Artificial Intelligence (AAAI). 259--264."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence (AAAI). 337--342","author":"Del Val A.","year":"2000","unstructured":"Del Val , A. 2000 a. The complexity of restricted consequence finding and abduction . In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI). 337--342 . Del Val, A. 2000a. The complexity of restricted consequence finding and abduction. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI). 337--342."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00088-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200838"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00179-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00040-9"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 62--67","author":"Eiter T.","unstructured":"Eiter , T. and Makino , K . 2002. On computing all abductive explanations . In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 62--67 . Eiter, T. and Makino, K. 2002. On computing all abductive explanations. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 62--67."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Eiter T. and Makino K. 2003a. Abduction and the dualization problem. In Discovery Science. 1--20.  Eiter T. and Makino K. 2003a. Abduction and the dualization problem. In Discovery Science. 1--20.","DOI":"10.1007\/978-3-540-39644-4_1"},{"key":"e_1_2_1_18_1","volume-title":"17th International Workshop on Computer Science Logic. 197--211","author":"Eiter T.","unstructured":"Eiter , T. and Makino , K . 2003b. Generating all abductive on horn theories . In 17th International Workshop on Computer Science Logic. 197--211 . Eiter, T. and Makino, K. 2003b. Generating all abductive on horn theories. In 17th International Workshop on Computer Science Logic. 197--211."},{"key":"e_1_2_1_19_1","volume-title":"ECAI Workshop on Abductive and Inductive Reasoning. http:\/\/www.cs.bris.ac.uk\/%7eflach\/ECAI96\/ECAI96report.html.","author":"Flach P.","unstructured":"Flach , P. and Kakas , A. , Eds . 1996 . ECAI Workshop on Abductive and Inductive Reasoning. http:\/\/www.cs.bris.ac.uk\/%7eflach\/ECAI96\/ECAI96report.html. Flach, P. and Kakas, A., Eds. 1996. ECAI Workshop on Abductive and Inductive Reasoning. http:\/\/www.cs.bris.ac.uk\/%7eflach\/ECAI96\/ECAI96report.html."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0606-3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0606-3"},{"key":"e_1_2_1_22_1","volume-title":"Eds","author":"Flach P.","year":"2000","unstructured":"Flach , P. and Kakas , A. , Eds . 2000 . Abduction and Induction. Essays on their Relation and Integration. Kluwer Academic , Hingham, MA. Flach, P. and Kakas, A., Eds. 2000. Abduction and Induction. Essays on their Relation and Integration. Kluwer Academic, Hingham, MA."},{"key":"e_1_2_1_23_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman San Francisco CA.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman San Francisco CA."},{"key":"e_1_2_1_24_1","volume-title":"Handbook of Theoretical Computer Science","author":"Johnson D. S.","unstructured":"Johnson , D. S. 1990. A catalog of complexity classes . In Handbook of Theoretical Computer Science , vol. A, J. van Leeuwen, Ed. Elsevier Science, North-Holland, Amsterdam. 67-- 161 . Johnson, D. S. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Science, vol. A, J. van Leeuwen, Ed. Elsevier Science, North-Holland, Amsterdam. 67--161."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804678"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI). 1061--1067","author":"Levesque H. J.","year":"1989","unstructured":"Levesque , H. J. 1989 . A knowledge-level account of abduction . In Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI). 1061--1067 . Levesque, H. J. 1989. A knowledge-level account of abduction. In Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI). 1061--1067."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504795"},{"key":"e_1_2_1_28_1","unstructured":"Liberatore P. and Schaerf M. 2002. Compilability of abduction. Tech. Rep. cs.AI\/0210007 Computing Research Repository (CoRR).  Liberatore P. and Schaerf M. 2002. Compilability of abduction. Tech. Rep. cs.AI\/0210007 Computing Research Repository (CoRR)."},{"key":"e_1_2_1_29_1","unstructured":"Peirce C. S. 1955. Abduction and induction. In Philosophical Writings of Peirce J. Buchler Ed. Dover New York. 150--156.  Peirce C. S. 1955. Abduction and induction. In Philosophical Writings of Peirce J. Buchler Ed. Dover New York. 150--156."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 16th National Conference on Artificial Intelligence (AAAI). 183--188","author":"Reiter R.","unstructured":"Reiter , R. and de Kleer, J. 1987. Foundations of assumption-based truth maintenace systems: Preliminary report . In Proceedings of the 16th National Conference on Artificial Intelligence (AAAI). 183--188 . Reiter, R. and de Kleer, J. 1987. Foundations of assumption-based truth maintenace systems: Preliminary report. In Proceedings of the 16th National Conference on Artificial Intelligence (AAAI). 183--188."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226644"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00069-7"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 343--348","author":"Selman B.","unstructured":"Selman , B. and Levesque , H. J . 1990. Abductive and default reasoning: A computational core . In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 343--348 . Selman, B. and Levesque, H. J. 1990. Abductive and default reasoning: A computational core. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 343--348."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90020-8"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622434.1622435"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1182613.1182615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T18:55:17Z","timestamp":1672253717000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1182613.1182615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1145\/1182613.1182615"],"URL":"https:\/\/doi.org\/10.1145\/1182613.1182615","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]},"assertion":[{"value":"2007-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}