{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T08:01:05Z","timestamp":1751702465233},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441441"},{"type":"electronic","value":"9783540457190"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45719-4_24","type":"book-chapter","created":{"date-parts":[[2007,10,9]],"date-time":"2007-10-09T10:55:00Z","timestamp":1191927300000},"page":"349-364","source":"Crossref","is-referenced-by-count":17,"title":["Algebraic Dynamic Programming"],"prefix":"10.1007","author":[{"given":"Robert","family":"Giegerich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,9,2]]},"reference":[{"key":"24_CR1","volume-title":"Data Structures and Algorithms","author":"A. V. Aho","year":"1983","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. Addison-Wesley, Reading, MA, USA, 1983."},{"key":"24_CR2","unstructured":"R. Bellman. Dynamic Programming. Princeton University Press, 1957."},{"key":"24_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-56625-2","volume-title":"From dynamic programming to greedy algorithms","author":"R. S. Bird","year":"1993","unstructured":"R. S. Bird and O. de Moor. From dynamic programming to greedy algorithms. In B. Moeller, editor, State-of-the-Art Seminar on Formal Program Development. Springer LNCS 755, 1993."},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0019-9958(69)90065-5","volume":"14","author":"W. S. Brainerd","year":"1969","unstructured":"W. S. Brainerd. Tree generating regular systems. Information and Control, 14:217\u2013231, 1969.","journal-title":"Information and Control"},{"key":"24_CR5","unstructured":"G. Brassard and P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988."},{"key":"24_CR6","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990."},{"key":"24_CR7","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":"24_CR8","doi-asserted-by":"crossref","unstructured":"R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis. Cambridge University Press, 1998.","DOI":"10.1017\/CBO9780511790492"},{"key":"24_CR9","unstructured":"D. Evers and R. Giegerich. Reducing the conformation space in RNA structure prediction. In German Conference on Bioinformatics, 2001."},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1093\/bioinformatics\/16.8.665","volume":"16","author":"R. Giegerich","year":"2000","unstructured":"R. Giegerich. A Systematic Approach to Dynamic Programming in Bioinformatics. Bioinformatics, 16:665\u2013677, 2000.","journal-title":"Bioinformatics"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"R. Giegerich. Explaining and controlling ambiguity in dynamic programming. In Proc. Combinatorial Pattern Matching, pages 46\u201359. Springer Verlag, 2000.","DOI":"10.1007\/3-540-45123-4_6"},{"key":"24_CR12","unstructured":"R. Giegerich, M. H\u00f6chsmann, and S. Kurtz. Local Similarity Problems on Trees: A Uniform Model and its Implementation. 2002. (submitted)."},{"key":"24_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-19027-9_17","volume-title":"Code selection techniques: Pattern matching, tree parsing and inversion of derivors","author":"R. Giegerich","year":"1988","unstructured":"R. Giegerich and K. Schmal. Code selection techniques: Pattern matching, tree parsing and inversion of derivors. In Proc. European Symposium on Programming 1988, pages 247\u2013268. Springer LNCS 300, 1988."},{"key":"24_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45442-X_1","volume-title":"Mathematics of Program Construction","author":"R. Giegerich","year":"2002","unstructured":"R. Giegerich and P. Steffen. Implementing algebraic dynamic programming in the functional and the imperative paradigm. In E. A. Boiten and B. M\u00f6ller, editors, Mathematics of Program Construction, pages 1\u201320. Springer LNCS 2386, 2002."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O. Gotoh","year":"1982","unstructured":"O. Gotoh. An improved algorithm for matching biological sequences. J. Mol. Biol., 162:705\u2013708, 1982.","journal-title":"J. Mol. Biol."},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"24_CR17","unstructured":"S. Kurtz. Fundamental Algorithms for a Declarative Pattern Matching System. Dissertation, Technische Fakult\u00e4t der Universit\u00e4t Bielefeld, 1995."},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Data structures and algorithms. Springer Verlag, 1984.","DOI":"10.1007\/978-3-642-69672-5"},{"key":"24_CR19","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1524\/zpch.2002.216.2.193","volume":"216","author":"C. Meyer","year":"2002","unstructured":"C. Meyer and R. Giegerich. Matching and Significance Evaluation of Combined Sequence-Structure Motifs in RNA. Z. Phys. Chem., 216:193\u2013216, 2002.","journal-title":"Z. Phys. Chem."},{"key":"24_CR20","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1287\/opre.12.4.610","volume":"12","author":"L. Mitten","year":"1964","unstructured":"L. Mitten. Composition principles for the synthesis of optimal multi-stage processes. Operations Research, 12:610\u2013619, 1964.","journal-title":"Operations Research"},{"key":"24_CR21","unstructured":"O. de Moor. Dynamic Programming as a Software Component. In M. Mastorakis, editor, Proceedings of CSCC, July 4\u20138, Athens. WSES Press, 1999."},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/0022-247X(82)90223-2","volume":"86","author":"T. L. Morin","year":"1982","unstructured":"T. L. Morin. Monotonicity and the principle of optimality. Journal of Mathematical Analysis and Applications, 86:665\u2013674, 1982.","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"24_CR23","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S. B. Needleman","year":"1970","unstructured":"S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol., 48:443\u2013453, 1970.","journal-title":"J. Mol. Biol."},{"key":"24_CR24","unstructured":"R. Sedgewick. Algorithms. Addison-Wesley, 2nd edition, 1989."},{"key":"24_CR25","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T. F. Smith","year":"1981","unstructured":"T. F. Smith and M. S. Waterman. The identification of common molecular subsequences. J. Mol. Biol., 147:195\u2013197, 1981.","journal-title":"J. Mol. Biol."},{"key":"24_CR26","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02459506","volume":"46","author":"M. Zuker","year":"1984","unstructured":"M. Zuker and S. Sankoff. RNA secondary structures and their prediction. Bull. Math. Biol., 46:591\u2013621, 1984.","journal-title":"Bull. Math. Biol."},{"issue":"1","key":"24_CR27","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M. Zuker","year":"1981","unstructured":"M. Zuker and P. Stiegler. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res., 9(1):133\u2013148, 1981.","journal-title":"Nucleic Acids Res."}],"container-title":["Lecture Notes in Computer Science","Algebraic Methodology and Software Technology"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45719-4_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T13:09:36Z","timestamp":1556888976000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45719-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441441","9783540457190"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-45719-4_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}