{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T01:05:42Z","timestamp":1777424742964,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,7,8]],"date-time":"2014-07-08T00:00:00Z","timestamp":1404777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF11103, W911NF09102, and W911NF11C02"],"award-info":[{"award-number":["W911NF11103, W911NF09102, and W911NF11C02"]}],"id":[{"id":"10.13039\/100000183","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":[[2014,7,8]]},"abstract":"<jats:p>\n            Annotated Probabilistic Temporal (APT) logic programs are a form of logic programs that allow users to state (or systems to automatically learn) rules of the form \u201cformula\n            <jats:italic>G<\/jats:italic>\n            becomes true \u0394\n            <jats:italic>t<\/jats:italic>\n            time units after formula\n            <jats:italic>F<\/jats:italic>\n            became true with \u2113 to\n            <jats:italic>u<\/jats:italic>\n            % probability.\u201d In this article, we deal with abductive reasoning in APT logic: given an APT logic program \u03a0, a set of formulas\n            <jats:italic>H<\/jats:italic>\n            that can be \u201cadded\u201d to \u03a0, and a (temporal) goal\n            <jats:italic>g<\/jats:italic>\n            , is there a subset\n            <jats:italic>S<\/jats:italic>\n            of\n            <jats:italic>H<\/jats:italic>\n            such that \u03a0 \u222a\n            <jats:italic>S<\/jats:italic>\n            is consistent and entails the goal\n            <jats:italic>g<\/jats:italic>\n            ? In general, there are many different solutions to the problem and some of them can be highly repetitive, differing only in some unimportant temporal aspects. We propose a compact representation called\n            <jats:italic>super-solutions<\/jats:italic>\n            that succinctly represent\n            <jats:italic>sets<\/jats:italic>\n            of such solutions. Super-solutions are compact, but lossless representations of sets of such solutions. We study the complexity of existence of basic, super-, and maximal super-solutions as well as check if a set is a solution\/super-solution\/maximal super-solution. We then leverage a geometric characterization of the problem to suggest a set of pruning strategies and interesting properties that can be leveraged to make the search of basic and super-solutions more efficient. We propose correct sequential algorithms to find solutions and super-solutions. In addition, we develop parallel algorithms to find basic and super-solutions.\n          <\/jats:p>","DOI":"10.1145\/2627354","type":"journal-article","created":{"date-parts":[[2014,7,24]],"date-time":"2014-07-24T15:46:18Z","timestamp":1406216778000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Super-Solutions"],"prefix":"10.1145","volume":"15","author":[{"given":"Cristian","family":"Molinaro","sequence":"first","affiliation":[{"name":"University of Calabria, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amy","family":"Sliva","sequence":"additional","affiliation":[{"name":"Northeastern University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. S.","family":"Subrahmanian","sequence":"additional","affiliation":[{"name":"University of Maryland College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00020-5"},{"key":"e_1_2_1_2_1","first-page":"461","article-title":"From basic agent behavior to strategic patterns in a robotic soccer domain","volume":"29","author":"Bezek A.","year":"2005","unstructured":"A. Bezek and M. Gams . 2005 . From basic agent behavior to strategic patterns in a robotic soccer domain . Informatica (Slovenia) 29 , 4 (2005), 461 -- 468 . A. Bezek and M. Gams. 2005. From basic agent behavior to strategic patterns in a robotic soccer domain. Informatica (Slovenia) 29, 4 (2005), 461--468.","journal-title":"Informatica (Slovenia)"},{"key":"e_1_2_1_3_1","volume-title":"Congress of the Italian Association for Artificial Intelligence (AI&ast;IA)","author":"Brusoni V.","year":"1997","unstructured":"V. Brusoni , L. Console , P. Terenziani , and D. T. Dupr\u00e9 . 1997. An efficient algorithm for temporal abduction . Congress of the Italian Association for Artificial Intelligence (AI&ast;IA) ( 1997 ), 195--206. V. Brusoni, L. Console, P. Terenziani, and D. T. Dupr\u00e9. 1997. An efficient algorithm for temporal abduction. Congress of the Italian Association for Artificial Intelligence (AI&ast;IA) (1997), 195--206."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90005-5"},{"key":"e_1_2_1_5_1","unstructured":"E. Charniak and R. Goldman. 1991. Probabilistic Abduction for Plan Recognition. Technical Report. Providence RI.   E. Charniak and R. Goldman. 1991. Probabilistic Abduction for Plan Recognition. Technical Report. Providence RI."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90060-O"},{"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","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1047764"},{"key":"e_1_2_1_9_1","volume-title":"European Conference on Artificial Intelligence (ECAI). 384--388","author":"Denecker M.","unstructured":"M. Denecker , L. Missiaen , and M. Bruynooghe . 1992. Temporal reasoning with abductive event calculus . In European Conference on Artificial Intelligence (ECAI). 384--388 . M. Denecker, L. Missiaen, and M. Bruynooghe. 1992. Temporal reasoning with abductive event calculus. In European Conference on Artificial Intelligence (ECAI). 384--388."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200838"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00040-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"U. Endress P. Mancarella F. Sadri G. Terreni and F. Toni. 2004. The CIFF proof procedure for abductive logic programming with constraints. Logics in Artificial Intelligence - Journes Europennes sur la Logique en Intelligence Artificielle (JELIA) (2004) 31--43.  U. Endress P. Mancarella F. Sadri G. Terreni and F. Toni. 2004. The CIFF proof procedure for abductive logic programming with constraints. Logics in Artificial Intelligence - Journes Europennes sur la Logique en Intelligence Artificielle (JELIA) (2004) 31--43.","DOI":"10.1007\/978-3-540-30227-8_6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90060-U"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/215206.215372"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(2000)51:2%3C95::AID-ASI2%3E3.0.CO;2-H"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2009.01.003"},{"key":"e_1_2_1_17_1","volume-title":"Probability logic. Notre Dame Journal of Formal Logic 25 (3)","author":"Hailperin T.","year":"1984","unstructured":"T. Hailperin . 1984. Probability logic. Notre Dame Journal of Formal Logic 25 (3) ( 1984 ), 198--212. T. Hailperin. 1984. Probability logic. Notre Dame Journal of Formal Logic 25 (3) (1984), 198--212."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/2.6.719"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IJCAI-09 Workshop on Plan, Activity, and Intent Recognition (PAIR-09)","author":"Kate R. J.","unstructured":"R. J. Kate and R. J. Mooney . 2009. Probabilistic abduction using Markov logic networks . In Proceedings of the IJCAI-09 Workshop on Plan, Activity, and Intent Recognition (PAIR-09) . Pasadena, CA. R. J. Kate and R. J. Mooney. 2009. Probabilistic abduction using Markov logic networks. In Proceedings of the IJCAI-09 Workshop on Plan, Activity, and Intent Recognition (PAIR-09). Pasadena, CA."},{"key":"e_1_2_1_20_1","volume-title":"Foundations of Logic Programming","author":"Lloyd J. W.","unstructured":"J. W. Lloyd . 1987. Foundations of Logic Programming ( 2 nd ed.). Springer . J. W. Lloyd. 1987. Foundations of Logic Programming (2nd ed.). Springer.","edition":"2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068409990093"},{"key":"e_1_2_1_22_1","volume-title":"International Conference on Logic Programming (ICLP), Technical Communications. 240--250","author":"Molinaro C.","unstructured":"C. Molinaro , A. Sliva , and V. S. Subrahmanian . 2011. Abduction in annotated probabilistic temporal logic . In International Conference on Logic Programming (ICLP), Technical Communications. 240--250 . C. Molinaro, A. Sliva, and V. S. Subrahmanian. 2011. Abduction in annotated probabilistic temporal logic. In International Conference on Logic Programming (ICLP), Technical Communications. 240--250."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90061-J"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90031-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90068-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Y. Peng and J. Reggia. 1990. Abductive Inference Models for Diagnostic Problem Solving. Springer-Verlag.   Y. Peng and J. Reggia. 1990. Abductive Inference Models for Diagnostic Problem Solving. Springer-Verlag.","DOI":"10.1007\/978-1-4419-8682-5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068404002224"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90061-F"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00027-1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1877714.1877720"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2159531.2159535"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00077-1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2480759.2480764"},{"key":"e_1_2_1_34_1","volume-title":"International Conference on Scalable Uncertainty Management (SUM). 319--332","author":"Simari G. I.","unstructured":"G. I. Simari , J. P. Dickerson , and V. S. Subrahmanian . 2010. Cost-based query answering in action probabilistic logic programs . In International Conference on Scalable Uncertainty Management (SUM). 319--332 . G. I. Simari, J. P. Dickerson, and V. S. Subrahmanian. 2010. Cost-based query answering in action probabilistic logic programs. In International Conference on Scalable Uncertainty Management (SUM). 319--332."},{"key":"e_1_2_1_35_1","volume-title":"International Conference on Logic Programming (ICLP), Technical Communications. 192--201","author":"Simari G. I.","unstructured":"G. I. Simari and V. S. Subrahmanian . 2010. Abductive inference in probabilistic logic programs . In International Conference on Logic Programming (ICLP), Technical Communications. 192--201 . G. I. Simari and V. S. Subrahmanian. 2010. Abductive inference in probabilistic logic programs. In International Conference on Logic Programming (ICLP), Technical Communications. 192--201."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"V. S. Subrahmanian A. Mannes J. Shakarian A. Sliva and J. Dickerson. 2013. Computational Analysis of Terror Groups: Lashkar-e-Taiba. Springer.   V. S. Subrahmanian A. Mannes J. Shakarian A. Sliva and J. Dickerson. 2013. Computational Analysis of Terror Groups: Lashkar-e-Taiba. Springer.","DOI":"10.1007\/978-1-4614-4769-6"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2627354","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2627354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:08Z","timestamp":1750229768000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2627354"}},"subtitle":["Succinctly Representing Solutions in Abductive Annotated Probabilistic Temporal Logic"],"short-title":[],"issued":{"date-parts":[[2014,7,8]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,7,8]]}},"alternative-id":["10.1145\/2627354"],"URL":"https:\/\/doi.org\/10.1145\/2627354","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,8]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}