{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:05:58Z","timestamp":1779836758238,"version":"3.53.1"},"reference-count":41,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2021,5,18]],"date-time":"2021-05-18T00:00:00Z","timestamp":1621296000000},"content-version":"unspecified","delay-in-days":137,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In this paper, we present a method for explaining the results produced by dynamic programming (DP) algorithms. Our approach is based on retaining a granular representation of values that are aggregated during program execution. The explanations that are created from the granular representations can answer questions of why one result was obtained instead of another and therefore can increase the confidence in the correctness of program results.<\/jats:p>\n                  <jats:p>Our focus on dynamic programming is motivated by the fact that dynamic programming offers a systematic approach to implementing a large class of optimization algorithms which produce decisions based on aggregated value comparisons. It is those decisions that the granular representation can help explain. Moreover, the fact that dynamic programming can be formalized using semirings supports the creation of a Haskell library for dynamic programming that has two important features. First, it allows programmers to specify programs by recurrence relationships from which efficient implementations are derived automatically. Second, the dynamic programs can be formulated generically (as type classes), which supports the smooth transition from programs that only produce result to programs that can run with granular representation and also produce explanations. Finally, we also demonstrate how to anticipate user questions about program results and how to produce corresponding explanations automatically in advance.<\/jats:p>","DOI":"10.1017\/s0956796821000083","type":"journal-article","created":{"date-parts":[[2021,5,18]],"date-time":"2021-05-18T02:42:17Z","timestamp":1621305737000},"update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":6,"title":["Explainable dynamic programming"],"prefix":"10.1017","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7471-4554","authenticated-orcid":false,"given":"MARTIN","family":"ERWIG","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"PRASHANT","family":"KUMAR","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2021,5,18]]},"reference":[{"key":"S0956796821000083_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/VLHCC.2005.42"},{"key":"S0956796821000083_ref15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S1571-0661(05)80538-9","article-title":"Debugging Haskell by observing intermediate data structures","volume":"41","author":"Gill","year":"2001","journal-title":"Electron. Notes Theoretical Comput. Sci."},{"key":"S0956796821000083_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9333-5"},{"key":"S0956796821000083_ref20","doi-asserted-by":"crossref","unstructured":"Khan, O. Z. , Poupart, P. & Black, J. P. (2009) Minimal sufficient explanations for factored Markov decision processes. In 19th International Conference on Automated Planning and Scheduling, pp. 194\u2013200.","DOI":"10.1609\/icaps.v19i1.13365"},{"key":"S0956796821000083_ref28","first-page":"321","article-title":"Semiring frameworks and algorithms for shortest-distance problems","volume":"7","author":"Mohri","year":"2002","journal-title":"J. Autom. Lang. Comb."},{"key":"S0956796821000083_ref39","doi-asserted-by":"publisher","DOI":"10.1145\/3388890"},{"key":"S0956796821000083_ref4","first-page":"19","volume-title":"The Knapsack Problem","author":"Bartholdi","year":"2008"},{"key":"S0956796821000083_ref11","doi-asserted-by":"publisher","DOI":"10.1287\/opre.5.2.266"},{"key":"S0956796821000083_ref8","volume-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"key":"S0956796821000083_ref2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2007.39"},{"key":"S0956796821000083_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/2505340"},{"key":"S0956796821000083_ref32","doi-asserted-by":"publisher","DOI":"10.1145\/1014007.1014020"},{"key":"S0956796821000083_ref21","unstructured":"Khoo, Y. P. , Foster, J. S. & Hicks, M. (2013) Expositor: Scriptable time-travel debugging with first-class traces. In ACM\/IEEE International Conference on Software Engineering, pp. 352\u2013361."},{"key":"S0956796821000083_ref17","first-page":"573","article-title":"Semiring parsing","volume":"25","author":"Goodman","year":"1999","journal-title":"Comput. Linguist."},{"key":"S0956796821000083_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"S0956796821000083_ref31","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008681016679"},{"key":"S0956796821000083_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s10515-006-0003-z"},{"key":"S0956796821000083_ref38","unstructured":"Rush, S. (2009) Semirings Library. https:\/\/github.com\/srush\/SemiRings\/tree\/master"},{"key":"S0956796821000083_ref19","unstructured":"Juozapaitis, Z. , Fern, A. , Koul, A. , Erwig, M. & Doshi-Velez, F. (2019). Explainable reinforcement learning via reward decomposition. In IJCAI\/ECAI Workshop on Explainable Artificial Intelligence, pp. 47\u201353."},{"key":"S0956796821000083_ref36","doi-asserted-by":"publisher","DOI":"10.1145\/3110258"},{"key":"S0956796821000083_ref27","doi-asserted-by":"publisher","DOI":"10.1038\/218019a0"},{"key":"S0956796821000083_ref40","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1986.289308"},{"key":"S0956796821000083_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/S095679680000109X"},{"key":"S0956796821000083_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/11546382_7"},{"key":"S0956796821000083_ref9","unstructured":"Biswas, S. K. (1997) Dynamic Slicing in Higher-Order Programming Languages. Ph.D. thesis."},{"key":"S0956796821000083_ref37","doi-asserted-by":"crossref","unstructured":"Roehm, T. , Tiarks, R. , Koschke, R. & Maalej, W. (2012) How do professional developers comprehend software? In 34th International Conference on Software Engineering, pp. 255\u2013265.","DOI":"10.1109\/ICSE.2012.6227188"},{"key":"S0956796821000083_ref13","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"S0956796821000083_ref5","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.66.1"},{"key":"S0956796821000083_ref25","volume-title":"Inference to the Best Explanation","author":"Lipton","year":"2004"},{"key":"S0956796821000083_ref33","doi-asserted-by":"crossref","unstructured":"Parnin, C. & Orso, A. (2011) Are automated debugging techniques actually helping programmers? International Symposium on Software Testing and Analysis, pp. 199\u2013209.","DOI":"10.1145\/2001420.2001445"},{"key":"S0956796821000083_ref10","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"S0956796821000083_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S1358246100005130"},{"key":"S0956796821000083_ref34","doi-asserted-by":"publisher","DOI":"10.1145\/2364527.2364579"},{"key":"S0956796821000083_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/985692.985712"},{"key":"S0956796821000083_ref12","unstructured":"Erwig, M. , Fern, A. , Murali, M. & Koul, A. (2018). Explaining deep adaptive programs via reward decomposition. In IJCAI\/ECAI Workshop on Explainable Artificial Intelligence, pp. 40\u201344."},{"key":"S0956796821000083_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/1518701.1518942"},{"key":"S0956796821000083_ref14","volume-title":"Forms of Explanation","author":"Garfinkel","year":"1981"},{"key":"S0956796821000083_ref6","first-page":"679","article-title":"A Markovian decision process","volume":"6","author":"Bellman","year":"1957","journal-title":"J. Math. Mech."},{"key":"S0956796821000083_ref41","doi-asserted-by":"publisher","DOI":"10.1145\/587051.587053"},{"key":"S0956796821000083_ref7","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"S0956796821000083_ref29","doi-asserted-by":"publisher","DOI":"10.1109\/MS.2006.105"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796821000083","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:36:54Z","timestamp":1779835014000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796821000083\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":41,"alternative-id":["S0956796821000083"],"URL":"https:\/\/doi.org\/10.1017\/s0956796821000083","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"\u00a9 The Author(s) 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}],"article-number":"e10"}}