{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:51:28Z","timestamp":1772373088824,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006754","name":"U.S. Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF0920072"],"award-info":[{"award-number":["W911NF0920072"]}],"id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA95500610405"],"award-info":[{"award-number":["FA95500610405"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0540216, SES0826886"],"award-info":[{"award-number":["0540216, SES0826886"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF0910206, W911NF1110344"],"award-info":[{"award-number":["W911NF0910206, W911NF1110344"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000077","name":"Division of Social and Economic Sciences","doi-asserted-by":"publisher","award":["0540216, SES0826886"],"award-info":[{"award-number":["0540216, SES0826886"]}],"id":[{"id":"10.13039\/100000077","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:p>\n            Action-probabilistic logic programs (\n            <jats:italic>ap<\/jats:italic>\n            -programs) are a class of probabilistic logic programs that have been extensively used during the last few years for modeling behaviors of entities. Rules in\n            <jats:italic>ap<\/jats:italic>\n            -programs have the form \u201cIf the environment in which entity\n            <jats:italic>E<\/jats:italic>\n            operates satisfies certain conditions, then the probability that\n            <jats:italic>E<\/jats:italic>\n            will take some action\n            <jats:italic>A<\/jats:italic>\n            is between\n            <jats:italic>L<\/jats:italic>\n            and\n            <jats:italic>U<\/jats:italic>\n            \u201d. Given an\n            <jats:italic>ap<\/jats:italic>\n            -program, we are interested in trying to change the environment, subject to some constraints, so that the probability that entity\n            <jats:italic>E<\/jats:italic>\n            takes some action (or combination of actions) is maximized. This is called the Basic Abductive Query Answering Problem (BAQA). We first formally define and study the complexity of BAQA, and then go on to provide an exact (exponential time) algorithm to solve it, followed by more efficient algorithms for specific subclasses of the problem. We also develop appropriate heuristics to solve BAQA efficiently.\n          <\/jats:p>\n          <jats:p>\n            The second problem, called the Cost-based Query Answering (CBQA) problem checks to see if there is some way of achieving a desired action (or set of actions) with a probability exceeding a threshold, given certain costs. We first formally define and study an exact (intractable) approach to CBQA, and then go on to propose a more efficient algorithm for a specific subclass of\n            <jats:italic>ap<\/jats:italic>\n            -programs that builds on the results for the basic version of this problem. We also develop the first algorithms for parallel evaluation of CBQA. We conclude with an extensive report on experimental evaluations performed over prototype implementations of the algorithms developed for both BAQA and CBQA, showing that our parallel algorithms work well in practice.\n          <\/jats:p>","DOI":"10.1145\/2480759.2480764","type":"journal-article","created":{"date-parts":[[2013,6,18]],"date-time":"2013-06-18T12:36:08Z","timestamp":1371558968000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Parallel Abductive Query Answering in Probabilistic Logic Programs"],"prefix":"10.1145","volume":"14","author":[{"given":"Gerardo I.","family":"Simari","sequence":"first","affiliation":[{"name":"University of Maryland College Park"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John P.","family":"Dickerson","sequence":"additional","affiliation":[{"name":"University of Maryland College Park"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amy","family":"Sliva","sequence":"additional","affiliation":[{"name":"University of Maryland College Park"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. S.","family":"Subrahmanian","sequence":"additional","affiliation":[{"name":"University of Maryland College Park"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Asal V. Carter J. and Wilkenfeld J. 2008. Ethnopolitical violence and terrorism in the Middle East. In Peace and Conflict 2008 J. Hewitt J. Wilkenfeld and T. Gurr Eds. Paradigm.  Asal V. Carter J. and Wilkenfeld J. 2008. Ethnopolitical violence and terrorism in the Middle East. In Peace and Conflict 2008 J. Hewitt J. Wilkenfeld and T. Gurr Eds. Paradigm."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Baldoni M. Giordano L. Martelli A. and Patti V. 1997. An abductive proof procedure for reasoning about actions in modal logic programming. In Selected Papers from the Workshop on Non-Monotonic Extensions of Logic Programming (NMELP\u201996). Springer 132--150.   Baldoni M. Giordano L. Martelli A. and Patti V. 1997. An abductive proof procedure for reasoning about actions in modal logic programming. In Selected Papers from the Workshop on Non-Monotonic Extensions of Logic Programming (NMELP\u201996) . Springer 132--150.","DOI":"10.1007\/BFb0023805"},{"key":"e_1_2_1_3_1","article-title":"A Markovian decision process","author":"Bellman R.","year":"1957","unstructured":"Bellman , R. 1957 . A Markovian decision process . J. Math. Mech. 6. Bellman, R. 1957. A Markovian decision process. J. Math. Mech. 6.","journal-title":"J. Math. Mech. 6."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.204905"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00033-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstb.2007.2061"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92243-8_5"},{"key":"e_1_2_1_8_1","volume-title":"Linear Programming","author":"Chvtal V.","unstructured":"Chvtal , V. 1983. Linear Programming . W.H.Freeman , New York . Chvtal, V. 1983. Linear Programming. W.H.Freeman, New York."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.1991.tb00388.x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022649401552"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS\u201996)","author":"de Bonet J. S.","unstructured":"de Bonet , J. S. , Isbell , C. L. Jr. , and Viola , P. A . 1996. MIMIC: Finding optima by estimating probability densities . In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS\u201996) . MIT Press, 424--430. de Bonet, J. S., Isbell, C. L. Jr., and Viola, P. A. 1996. MIMIC: Finding optima by estimating probability densities. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS\u201996). MIT Press, 424--430."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Denecker M. and Kakas A. C. 2002. Abduction in logic programming. In Computational Logic: Logic Programming and Beyond Essays in Honour of Robert A. Kowalski Part I Springer 402--436.   Denecker M. and Kakas A. C. 2002. Abduction in logic programming. In Computational Logic: Logic Programming and Beyond Essays in Honour of Robert A. Kowalski Part I Springer 402--436.","DOI":"10.1007\/3-540-45628-7_16"},{"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 International Conference on Logic Programming. 562--579","author":"Eshghi K.","year":"1988","unstructured":"Eshghi , K. 1988 . Abductive planning with event calculus . In Proceedings of the International Conference on Logic Programming. 562--579 . Eshghi, K. 1988. Abductive planning with event calculus. In Proceedings of the International Conference on Logic Programming. 562--579."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90060-U"},{"key":"e_1_2_1_18_1","unstructured":"Giles J. 2008. Can conflict forecasts predict violence hotspots? New Scientist 2647.  Giles J. 2008. Can conflict forecasts predict violence hotspots? New Scientist 2647."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093870625"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1656274.1656278"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference on Information Processing and Management of Uncertainty, L. Magdalena, M. Ojeda-Aciego, and J. L. Verdegay Eds., 9--16","author":"Josang A.","year":"2008","unstructured":"Josang , A. 2008 . Abductive reasoning with uncertainty . In Proceedings of the Conference on Information Processing and Management of Uncertainty, L. Magdalena, M. Ojeda-Aciego, and J. L. Verdegay Eds., 9--16 . Josang, A. 2008. Abductive reasoning with uncertainty. In Proceedings of the Conference on Information Processing and Management of Uncertainty, L. Magdalena, M. Ojeda-Aciego, and J. L. Verdegay Eds., 9--16."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00075-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.003"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-008-9089-2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014482025714"},{"key":"e_1_2_1_27_1","volume-title":"Foundations of Logic Programming","author":"Lloyd J. W.","unstructured":"Lloyd , J. W. 1987. Foundations of Logic Programming 2 nd Ed. Springer . Lloyd, J. W. 1987. Foundations of Logic Programming 2nd Ed. Springer.","edition":"2"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the International Conference on Computer and Communication Devices.","author":"Mannes A.","unstructured":"Mannes , A. , Michael , M. , Pate , A. , Sliva , A. , Subrahmanian , V. S. , and Wilkenfeld , J . 2008a. Stochastic opponent modeling agents: A case study with Hamas . In Proceedings of the International Conference on Computer and Communication Devices. Mannes, A., Michael, M., Pate, A., Sliva, A., Subrahmanian, V. S., and Wilkenfeld, J. 2008a. Stochastic opponent modeling agents: A case study with Hamas. In Proceedings of the International Conference on Computer and Communication Devices."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 1st International Workshop on Social Computing, Behavioral Modeling, and Prediction. H. Liu and J. Salerno Eds.","author":"Mannes A.","unstructured":"Mannes , A. , Michael , M. , Pate , A. , Sliva , A. , Subrahmanian , V. S. , and Wilkenfeld , J . 2008b. Stochastic opponent modelling agents: A case study with Hezbollah . In Proceedings of the 1st International Workshop on Social Computing, Behavioral Modeling, and Prediction. H. Liu and J. Salerno Eds. Mannes, A., Michael, M., Pate, A., Sliva, A., Subrahmanian, V. S., and Wilkenfeld, J. 2008b. Stochastic opponent modelling agents: A case study with Hezbollah. In Proceedings of the 1st International Workshop on Social Computing, Behavioral Modeling, and Prediction. H. Liu and J. Salerno Eds."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90061-J"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00881836"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90031-7"},{"key":"e_1_2_1_33_1","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl J.","unstructured":"Pearl , J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . Morgan Kaufmann Publishers Inc ., San Francisco. Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the AAAI Spring Symposium on Abduction. AAAI Press","author":"Pearl J.","year":"1991","unstructured":"Pearl , J. 1991 . Probabilistic and qualitative abduction . In Proceedings of the AAAI Spring Symposium on Abduction. AAAI Press , Stanford, CA, 155--158. Pearl, J. 1991. Probabilistic and qualitative abduction. In Proceedings of the AAAI Spring Symposium on Abduction. AAAI Press, Stanford, CA, 155--158."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013500812258"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Peng Y. and Reggia J. A. 1990. Abductive Inference Models for Diagnostic Problem-Solving. Springer.   Peng Y. and Reggia J. A. 1990. Abductive Inference Models for Diagnostic Problem-Solving . Springer.","DOI":"10.1007\/978-1-4419-8682-5"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90061-F"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00027-1"},{"key":"e_1_2_1_39_1","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman M.","unstructured":"Puterman , M. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley & Sons . Puterman, M. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00077-1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90022-W"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00114724"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 10th Yale Workshop on Adaptive and Learning Systems.","author":"Williams R.","unstructured":"Williams , R. and Baird , L . 1994. Tight performance bounds on greedy policies based on imperfect value functions . In Proceedings of the 10th Yale Workshop on Adaptive and Learning Systems. Williams, R. and Baird, L. 1994. Tight performance bounds on greedy policies based on imperfect value functions. In Proceedings of the 10th Yale Workshop on Adaptive and Learning Systems."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2480759.2480764","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2480759.2480764","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:14Z","timestamp":1750235954000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2480759.2480764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1145\/2480759.2480764"],"URL":"https:\/\/doi.org\/10.1145\/2480759.2480764","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2010-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}