{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:17:36Z","timestamp":1725794256932},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319071503"},{"type":"electronic","value":"9783319071510"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07151-0_12","type":"book-chapter","created":{"date-parts":[[2014,5,21]],"date-time":"2014-05-21T23:30:14Z","timestamp":1400715014000},"page":"186-202","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Programming via Thinning and Incrementalization"],"prefix":"10.1007","author":[{"given":"Akimasa","family":"Morihata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masato","family":"Koishi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atsushi","family":"Ohori","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"de Moor, O.: Categories, Relations and Dynamic Programming. PhD thesis, Oxford University Computing Laboratory, Technical Monograph PRG-98 (1992)"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Bird, R.S., de Moor, O.: Algebra of Programming. Prentice Hall (1997)","DOI":"10.1007\/978-3-642-61455-2_12"},{"issue":"4","key":"12_CR3","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1017\/S0956796801004038","volume":"11","author":"R.S. Bird","year":"2001","unstructured":"Bird, R.S.: Maximum marking problems. J. Funct. Program.\u00a011(4), 411\u2013424 (2001)","journal-title":"J. Funct. Program."},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0026809","volume-title":"Programming Languages: Implementations, Logics and Programs","author":"O. Moor de","year":"1995","unstructured":"de Moor, O.: A generic program for sequential decision processes. In: Swierstra, S.D. (ed.) PLILP 1995. LNCS, vol.\u00a0982, pp. 1\u201323. Springer, Heidelberg (1995)"},{"issue":"2","key":"12_CR5","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1145\/234528.234529","volume":"28","author":"A. Pettorossi","year":"1996","unstructured":"Pettorossi, A., Proietti, M.: Rules and strategies for transforming functional and logic programs. ACM Computing Surveys\u00a028(2), 360\u2013414 (1996)","journal-title":"ACM Computing Surveys"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Sasano, I., Hu, Z., Takeichi, M., Ogawa, M.: Make it practical: a generic linear-time algorithm for solving maximum-weightsum problems. In: Proceedings of the 5th ACM SIGPLAN International Conference on Functional Programming, ICFP 2000, pp. 137\u2013149. ACM Press (2000)","DOI":"10.1145\/351240.351254"},{"issue":"1-2","key":"12_CR7","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1023\/A:1023068020483","volume":"16","author":"Y.A. Liu","year":"2003","unstructured":"Liu, Y.A., Stoller, S.D.: Dynamic programming via static incrementalization. Higher-Order and Symbolic Computation\u00a016(1-2), 37\u201362 (2003)","journal-title":"Higher-Order and Symbolic Computation"},{"issue":"3","key":"12_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","volume":"51","author":"R. Giegerich","year":"2004","unstructured":"Giegerich, R., Meyer, C., Steffen, P.: A discipline of dynamic programming over sequence data. Sci. Comput. Program.\u00a051(3), 215\u2013263 (2004)","journal-title":"Sci. Comput. Program."},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/1053468.1053471","volume":"27","author":"Y.A. Liu","year":"2005","unstructured":"Liu, Y.A., Stoller, S.D., Li, N., Rothamel, T.: Optimizing aggregate array computations in loops. ACM Trans. Program. Lang. Syst.\u00a027(1), 91\u2013125 (2005)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1007\/11560647_37","volume-title":"Theoretical Aspects of Computing \u2013 ICTAC 2005","author":"I. Sasano","year":"2005","unstructured":"Sasano, I., Ogawa, M., Hu, Z.: Maximum marking problems with accumulative weight functions. In: Van Hung, D., Wirsing, M. (eds.) ICTAC 2005. LNCS, vol.\u00a03722, pp. 562\u2013578. Springer, Heidelberg (2005)"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Puchinger, J., Stuckey, P.J.: Automating branch-and-bound for dynamic programs. In: Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, PEPM 2008, pp. 81\u201389. ACM Press (2008)","DOI":"10.1145\/1328408.1328421"},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00354-010-0098-4","volume":"29","author":"A. Morihata","year":"2011","unstructured":"Morihata, A.: A short cut to optimal sequences. New Generation Comput.\u00a029(1), 31\u201359 (2011)","journal-title":"New Generation Comput."},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Pu, Y., Bod\u00edk, R., Srivastava, S.: Synthesis of first-order dynamic programming algorithms. In: Lopes, C.V., Fisher, K. (eds.) Proceedings of the 26th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2011, pp. 83\u201398. ACM Press (2011)","DOI":"10.1145\/2048066.2048076"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Sauthoff, G., Janssen, S., Giegerich, R.: Bellman\u2019s gap: a declarative language for dynamic programming. In: Proceedings of the 13th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, pp. 29\u201340. ACM Press (2011)","DOI":"10.1145\/2003476.2003484"},{"issue":"3","key":"12_CR15","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1145\/357172.357177","volume":"4","author":"R. Paige","year":"1982","unstructured":"Paige, R., Koenig, S.: Finite differencing of computable expressions. ACM Trans. Program. Lang. Syst.\u00a04(3), 402\u2013454 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"3","key":"12_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0167-6423(88)90033-0","volume":"11","author":"J. Cai","year":"1989","unstructured":"Cai, J., Paige, R.: Program derivation by fixed point computation. Sci. Comput. Program.\u00a011(3), 197\u2013261 (1989)","journal-title":"Sci. Comput. Program."},{"issue":"1","key":"12_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-6423(94)00031-9","volume":"24","author":"Y.A. Liu","year":"1995","unstructured":"Liu, Y.A., Teitelbaum, T.: Systematic derivation of incremental programs. Sci. Comput. Program.\u00a024(1), 1\u201339 (1995)","journal-title":"Sci. Comput. Program."},{"issue":"3","key":"12_CR18","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1145\/291889.291895","volume":"20","author":"Y.A. Liu","year":"1998","unstructured":"Liu, Y.A., Stoller, S.D., Teitelbaum, T.: Static caching for incremental computation. ACM Trans. Program. Lang. Syst.\u00a020(3), 546\u2013585 (1998)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"12_CR19","volume-title":"Introduction to algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to algorithms. MIT Press, Cambridge (2001)"},{"key":"12_CR20","unstructured":"Kleinberg, J., Tardos, \u00c9.: Algorithm Design Pearson Education Inc. (2006)"},{"issue":"1","key":"12_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcss.1998.1595","volume":"58","author":"T. Fukuda","year":"1999","unstructured":"Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Mining optimized association rules for numeric attributes. J. Comput. Syst. Sci.\u00a058(1), 1\u201312 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"12_CR22","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1145\/383891.383893","volume":"26","author":"T. Fukuda","year":"2001","unstructured":"Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Data mining with optimized two-dimensional association rules. ACM Trans. Database Syst.\u00a026(2), 179\u2013213 (2001)","journal-title":"ACM Trans. Database Syst."},{"volume-title":"Haskell 98 Language and Libraries: The Revised Report","year":"2003","key":"12_CR23","unstructured":"Peyton Jones, S. (ed.): Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, Cambridge (2003)"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Imielinski, T., Swami, A.N.: Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pp. 207\u2013216. ACM Press (1993)","DOI":"10.1145\/170035.170072"},{"key":"12_CR25","unstructured":"Koishi, M.: Derivation of two-dimensional maximum weighted sum problems using program transformations. Master\u2019s thesis, Graduate School of Information Science, Tohoku University (2013) (in Japanese)"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Mu, S.C.: Maximum segment sum is back: deriving algorithms for two segment problems with bounded lengths. In: Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, PEPM 2008, pp. 31\u201339. ACM Press (2008)","DOI":"10.1145\/1328408.1328414"},{"issue":"12","key":"12_CR27","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1145\/361227.361235","volume":"18","author":"J.T. Schwartz","year":"1975","unstructured":"Schwartz, J.T.: Automatic data structure choice in a language of very high level. Commun. ACM\u00a018(12), 722\u2013728 (1975)","journal-title":"Commun. ACM"},{"issue":"2","key":"12_CR28","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1145\/357133.357135","volume":"3","author":"E. Schonberg","year":"1981","unstructured":"Schonberg, E., Schwartz, J.T., Sharir, M.: An automatic technique for selection of data structures in SETL programs. ACM Trans. Program. Lang. Syst.\u00a03(2), 126\u2013143 (1981)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"12_CR29","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/S0747-7171(87)80066-4","volume":"4","author":"R. Paige","year":"1987","unstructured":"Paige, R., Henglein, F.: Mechanical translation of set theoretic problem specifications into efficient ram code\u2014a case study. J. Symb. Comput.\u00a04(2), 207\u2013232 (1987)","journal-title":"J. Symb. Comput."}],"container-title":["Lecture Notes in Computer Science","Functional and Logic Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07151-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T14:37:09Z","timestamp":1565447829000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07151-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319071503","9783319071510"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07151-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}