{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:56:42Z","timestamp":1725487002309},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540656999"},{"type":"electronic","value":"9783540490999"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-49099-x_19","type":"book-chapter","created":{"date-parts":[[2007,6,24]],"date-time":"2007-06-24T17:03:21Z","timestamp":1182704601000},"page":"288-305","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Programming via Static Incrementalization"],"prefix":"10.1007","author":[{"given":"Yanhong A.","family":"Liu","sequence":"first","affiliation":[]},{"given":"Scott D.","family":"Stoller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,28]]},"reference":[{"key":"19_CR1","volume-title":"Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming","author":"M. Abadi","year":"1996","unstructured":"M. Abadi, B. Lampson, and J.-J. L\u00e9vy. Analysis and caching of dependencies. In Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming. ACM, New York, May 1996."},{"key":"19_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974."},{"issue":"2","key":"19_CR3","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1109\/32.21743","volume":"15","author":"F. L. Bauer","year":"1989","unstructured":"F. L. Bauer, B. M\u00f6ller, H. Partsch, and P. Pepper. Formal program construction by transformations \u2014 Computer-aided, intuition-guided programming. IEEE Trans. Softw. Eng., 15(2):165\u2013180, Feb. 1989.","journal-title":"IEEE Trans. Softw. Eng."},{"key":"19_CR4","volume-title":"Dynamic Programming","author":"R. E. Bellman","year":"1957","unstructured":"R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, New Jersey, 1957."},{"issue":"4","key":"19_CR5","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/356827.356831","volume":"12","author":"R. S. Bird","year":"1980","unstructured":"R. S. Bird. Tabulation techniques for recursive programs. ACM Comput. Surv., 12(4):403\u2013417, Dec. 1980.","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"19_CR6","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1145\/1780.1781","volume":"6","author":"R. S. Bird","year":"1984","unstructured":"R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487\u2013504, Oct. 1984.","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"19_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/3-540-57499-9_16","volume-title":"Formal Program Development","author":"R. S. Bird","year":"1993","unstructured":"R. S. Bird and O. de Moor. From dynamic programming to greedy algorithms. In B. M\u00f6ller, H. Partsch, and S. Schuman, editors, Formal Program Development, volume 755 of Lecture Notes in Computer Science, pages 43\u201361. Springer-Verlag, Berlin, 1993."},{"issue":"2","key":"19_CR8","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0167-6423(92)90008-Y","volume":"18","author":"E. A. Boiten","year":"1992","unstructured":"E. A. Boiten. Improving recursive functions by inverting the order of evaluation. Sci. Comput. Program., 18(2):139\u2013179, Apr. 1992.","journal-title":"Sci. Comput. Program."},{"issue":"1","key":"19_CR9","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/321992.321996","volume":"24","author":"R. M. Burstall","year":"1977","unstructured":"R. M. Burstall and J. Darlington. A transformation system for developing recursive programs. J. ACM, 24(1):44\u201367, Jan. 1977.","journal-title":"J. ACM"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1145\/154630.154643","volume-title":"Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation","author":"W.-N. Chin","year":"1993","unstructured":"W.-N. Chin. Towards an automated tupling strategy. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 119\u2013132. ACM, New York, June 1993."},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"W.-N. Chin and M. Hagiya. A bounds inference method for vector-based memorization. In ICFP 1997 [23], pages 176\u2013187.","DOI":"10.1145\/258949.258965"},{"key":"19_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/3-540-57264-3_35","volume-title":"Proceedings of the 3rd International Workshop on Static Analysis","author":"W.-N. Chin","year":"1993","unstructured":"W.-N. Chin and S.-C. Khoo. Tupling functions with multiple recursion parameters. In P. Cousot, M. Falaschi, G. Fil\u00e9, and A. Rauzy, editors, Proceedings of the 3rd International Workshop on Static Analysis, volume 724 of Lecture Notes in Computer Science, pages 124\u2013140. Springer-Verlag, Berlin, Sept. 1993."},{"issue":"3","key":"19_CR13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1145\/2166.2167","volume":"5","author":"N. H. Cohen","year":"1983","unstructured":"N. H. Cohen. Eliminating redundant recursive calls. ACM Trans. Program. Lang. Syst., 5(3):265\u2013299, July 1983.","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"19_CR14","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press\/McGraw-Hill, 1990."},{"key":"19_CR15","first-page":"1","volume-title":"Algorithmic Languages and Calculi","author":"S. Curtis","year":"1997","unstructured":"S. Curtis. Dynamic programming: A different perspective. In R. Bird and L. Meertens, editors, Algorithmic Languages and Calculi, pages 1\u201323. Chapman & Hall, London, U.K., 1997."},{"key":"19_CR16","series-title":"Lect Notes Comput Sci","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":"O. de Moor. A generic program for sequential decision processes. In M. Hermenegildo and D. S. Swierstra, editors, Programming Languages: Implementations, Logics, and Programs, volume 982 of Lecture Notes in Computer Science, pages 1\u201323. Springer-Verlag, Berlin, 1995."},{"key":"19_CR17","unstructured":"O. de Moor and J. Gibbons. Bridging the algorithm gap: A linear-time functional program for paragraph formatting. Technical Report CMS-TR-97-03, School of Computing and Mathematical Sciences, Oxford Brookes University, July 1997."},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/91556.91679","volume-title":"Proceedings of the 1990 ACM Conference on LISP and Functional Programming","author":"J. Field","year":"1990","unstructured":"J. Field and T. Teitelbaum. Incremental reduction in the lambda calculus. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming, pages 307\u2013322. ACM, New York, June 1990."},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1145\/800205.806326","volume-title":"Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation","author":"D. P. Friedman","year":"1976","unstructured":"D. P. Friedman, D. S. Wise, and M. Wand. Recursive programming through table look-up. In Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, pages 85\u201389. ACM, New York, 1976."},{"key":"19_CR20","first-page":"133","volume-title":"Partial Evaluation and Mixed Computation","author":"Y. Futamura","year":"1988","unstructured":"Y. Futamura and K. Nogi. Generalized partial evaluation. In B. Bj\u00f8 rner, A. P. Ershov, and N. D. Jones, editors, Partial Evaluation and Mixed Computation, pages 133\u2013151. North-Holland, Amsterdam, 1988."},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Z. Hu, H. Iwasaki, M. Takeichi, and A. Takano. Tupling calculation eliminates multiple data traversals. In ICFP 1997 [23], pages 164\u2013175.","DOI":"10.1145\/258948.258964"},{"key":"19_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/3-540-15975-4_34","volume-title":"Proceedings of the 2nd Conference on Functional Programming Languages and Computer Architecture","author":"J. Hughes","year":"1985","unstructured":"J. Hughes. Lazy memo-functions. In Proceedings of the 2nd Conference on Functional Programming Languages and Computer Architecture, volume 201 of Lecture Notes in Computer Science, pages 129\u2013146. Springer-Verlag, Berlin, Sept. 1985."},{"key":"19_CR23","unstructured":"Proceedings of the 1997 ACM SIGPLAN International Conference on Functional Programming. ACM, New York, June 1997."},{"issue":"1","key":"19_CR24","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/5001.5004","volume":"8","author":"R. M. Keller","year":"1986","unstructured":"R. M. Keller and M. R. Sleep. Applicative caching. ACM Trans. Program. Lang. Syst., 8(1):88\u2013108, Jan. 1986.","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"19_CR25","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BF02983374","volume":"28","author":"H. Khoshnevisan","year":"1990","unstructured":"H. Khoshnevisan. Efficient memo-table management strategies. Acta Informatica, 28(1):43\u201381, 1990.","journal-title":"Acta Informatica"},{"key":"19_CR26","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1109\/KBSE.1995.490115","volume-title":"Proceedings of the 10th Knowledge-Based Software Engineering Conference","author":"Y. A. Liu","year":"1995","unstructured":"Y. A. Liu. CACHET: An interactive, incremental-attribution-based program transformation system for deriving incremental programs. In Proceedings of the 10th Knowledge-Based Software Engineering Conference, pages 19\u201326. IEEE CS Press, Los Alamitos, Calif., Nov. 1995."},{"key":"19_CR27","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/978-0-387-35264-0_14","volume-title":"Algorithmic Languages and Calculi","author":"Y. A. Liu","year":"1997","unstructured":"Y. A. Liu. Principled strength reduction. In R. Bird and L. Meertens, editors, Algorithmic Languages and Calculi, pages 357\u2013381. Chapman & Hall, London, U.K., 1997."},{"key":"19_CR28","first-page":"206","volume-title":"Proceedings of the IEEE 1998 International Conference on Computer Languages","author":"Y. A. Liu","year":"1998","unstructured":"Y. A. Liu. Dependence analysis for recursive data. In Proceedings of the IEEE 1998 International Conference on Computer Languages, pages 206\u2013215. IEEE CS Press, Los Alamitos, Calif., May 1998."},{"key":"19_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BFb0057778","volume-title":"Proceedings of the ACM SIGPLAN 1998 Workshop on Languages, Compilers, and Tools for Embedded Systems","author":"Y. A. Liu","year":"1998","unstructured":"Y. A. Liu and G. G\u00f3mez. Automatic accurate time-bound analysis for high-level languages. In Proceedings of the ACM SIGPLAN 1998 Workshop on Languages, Compilers, and Tools for Embedded Systems, volume 1474 of Lecture Notes in Computer Science, pages 31\u201340. Springer-Verlag, June 1998."},{"key":"19_CR30","first-page":"262","volume-title":"Proceedings of the IEEE 1998 International Conference on Computer Languages","author":"Y. A. Liu","year":"1998","unstructured":"Y. A. Liu and S. D. Stoller. Loop optimization for aggregate array computations. In Proceedings of the IEEE 1998 International Conference on Computer Languages, pages 262\u2013271. IEEE CS Press, Los Alamitos, Calif., May 1998."},{"key":"19_CR31","first-page":"157","volume-title":"Conference Record of the 23rd Annual ACM Symposium on Principles of Programming Languages","author":"Y. A. Liu","year":"1996","unstructured":"Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Discovering auxiliary information for incremental computation. In Conference Record of the 23rd Annual ACM Symposium on Principles of Programming Languages, pages 157\u2013170. ACM, New York, Jan. 1996."},{"issue":"3","key":"19_CR32","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1145\/291889.291895","volume":"20","author":"Y. A. Liu","year":"1998","unstructured":"Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Trans. Program. Lang. Syst., 20(3):546\u2013585, May 1998.","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"19_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-6423(94)00031-9","volume":"24","author":"Y. A. Liu","year":"1995","unstructured":"Y. A. Liu and T. Teitelbaum. Systematic derivation of incremental programs. Sci. Comput. Program., 24(1):1\u201339, Feb. 1995.","journal-title":"Sci. Comput. Program."},{"key":"19_CR34","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1038\/218019a0","volume":"218","author":"D. Michie","year":"1968","unstructured":"D. Michie. \u201cmemo\u201d functions and machine learning. Nature, 218:19\u201322, Apr. 1968.","journal-title":"Nature"},{"key":"19_CR35","first-page":"165","volume-title":"Proceedings of the 9th International Joint Conference on Artificial Intelligence","author":"D. J. Mostow","year":"1985","unstructured":"D. J. Mostow and D. Cohen. Automating program speedup by deciding what to cache. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, pages 165\u2013172. Morgan Kaufmann Publishers, San Francisco, Calif., Aug. 1985."},{"key":"19_CR36","doi-asserted-by":"crossref","unstructured":"R. Paige. Programming with invariants. IEEE Software, pages 56\u201369, Jan. 1986.","DOI":"10.1109\/MS.1986.233070"},{"key":"19_CR37","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/3-540-52592-0_54","volume-title":"Proceedings of the 3rd European Symposium on Programming","author":"R. Paige","year":"1990","unstructured":"R. Paige. Symbolic finite differencing \u2014 Part I. In Proceedings of the 3rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science, pages 36\u201356. Springer-Verlag, Berlin, May 1990."},{"issue":"3","key":"19_CR38","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1145\/357172.357177","volume":"4","author":"R. Paige","year":"1982","unstructured":"R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Trans. Program. Lang. Syst., 4(3):402\u2013454, July 1982.","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"19_CR39","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61512-2","volume-title":"Specification and Transformation of Programs \u2014 A Formal Approach to Software Development","author":"H. A. Partsch","year":"1990","unstructured":"H. A. Partsch. Specification and Transformation of Programs \u2014 A Formal Approach to Software Development. Springer-Verlag, Berlin, 1990."},{"key":"19_CR40","volume-title":"Conference Record of the 1984 ACM Symposium on LISP and Functional Programming","author":"A. Pettorossi","year":"1984","unstructured":"A. Pettorossi. A powerful strategy for deriving efficient programs by transformation. In Conference Record of the 1984 ACM Symposium on LISP and Functional Programming. ACM, New York, Aug. 1984."},{"issue":"2","key":"19_CR41","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1145\/234528.234529","volume":"28","author":"A. Pettorossi","year":"1996","unstructured":"A. Pettorossi and M. Proietti. Rules and strategies for transforming functional and logic programs. ACM Comput. Surv., 28(2):360\u2013414, June 1996.","journal-title":"ACM Comput. Surv."},{"key":"19_CR42","volume-title":"Algorithmic Languages and Calculi","author":"A. Pettorossi","year":"1997","unstructured":"A. Pettorossi and M. Proietti. Program derivation via list introduction. In R. Bird and L. Meertens, editors, Algorithmic Languages and Calculi. Chapman & Hall, London, U.K., 1997."},{"key":"19_CR43","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/62678.62719","volume-title":"Proceedings of the 1988 ACM Conference on LISP and Functional Programming","author":"W. Pugh","year":"1988","unstructured":"W. Pugh. An improved cache replacement strategy for function caching. In Proceedings of the 1988 ACM Conference on LISP and Functional Programming, pages 269\u2013276. ACM, New York, July 1988."},{"key":"19_CR44","doi-asserted-by":"crossref","unstructured":"W. Pugh. The Omega Test: A fast and practical integer programming algorithm for dependence analysis. Commun. ACM, 31(8), Aug. 1992.","DOI":"10.1145\/135226.135233"},{"key":"19_CR45","first-page":"315","volume-title":"Conference Record of the 16th Annual ACM Symposium on Principles of Programming Languages","author":"W. Pugh","year":"1989","unstructured":"W. Pugh and T. Teitelbaum. Incremental computation via function caching. In Conference Record of the 16th Annual ACM Symposium on Principles of Programming Languages, pages 315\u2013328. ACM, New York, Jan. 1989."},{"key":"19_CR46","unstructured":"P. W. Purdom and C. A. Brown. The Analysis of Algorithms. Holt, Rinehart and Winston, 1985."},{"key":"19_CR47","volume-title":"The Synthesizer Generator: A System for Constructing Language-Based Editors","author":"T. Reps","year":"1988","unstructured":"T. Reps and T. Teitelbaum. The Synthesizer Generator: A System for Constructing Language-Based Editors. Springer-Verlag, New York, 1988."},{"key":"19_CR48","first-page":"41","volume-title":"Conference Record of the 8th Annual ACM Symposium on Principles of Programming Languages","author":"W. L. Scherlis","year":"1981","unstructured":"W. L. Scherlis. Program improvement by internal specialization. In Conference Record of the 8th Annual ACM Symposium on Principles of Programming Languages, pages 41\u201349. ACM, New York, Jan. 1981."},{"issue":"9","key":"19_CR49","doi-asserted-by":"publisher","first-page":"1024","DOI":"10.1109\/32.58788","volume":"16","author":"D. R. Smith","year":"1990","unstructured":"D. R. Smith. KIDS: A semiautomatic program development system. IEEE Trans. Softw. Eng., 16(9):1024\u20131043, Sept. 1990.","journal-title":"IEEE Trans. Softw. Eng."},{"key":"19_CR50","first-page":"91","volume-title":"Constructing Programs from Specifications","author":"D. R. Smith","year":"1991","unstructured":"D. R. Smith. Structure and design of problem reduction generators. In B. M\u00f6ller, editor, Constructing Programs from Specifications, pages 91\u2013124. North-Holland, Amsterdam, 1991."},{"key":"19_CR51","volume-title":"Dynamic Programming","author":"M. Sniedovich","year":"1992","unstructured":"M. Sniedovich. Dynamic Programming. Marcel Dekker, New York, 1992."},{"issue":"2","key":"19_CR52","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/TSE.1976.233533","volume":"SE-2","author":"B. Wegbreit","year":"1976","unstructured":"B. Wegbreit. Goal-directed program transformation. IEEE Trans. Softw. Eng., SE-2(2):69\u201380, June 1976.","journal-title":"IEEE Trans. Softw. Eng."}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49099-X_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T05:32:57Z","timestamp":1556515977000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49099-X_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540656999","9783540490999"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/3-540-49099-x_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}