{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T16:33:37Z","timestamp":1689611617368},"reference-count":66,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T00:00:00Z","timestamp":1236124800000},"content-version":"unspecified","delay-in-days":5482,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[1994,3]]},"abstract":"<jats:p>Dynamic programming is a strategy for solving optimisation problems. In this paper, we show how many problems that may be solved by dynamic programming are instances of the same abstract specification. This specification is phrased using the calculus of relations offered by topos theory. The main theorem underlying dynamic programming can then be proved by straightforward equational reasoning.<\/jats:p><jats:p>The generic specification of dynamic programming makes use of higher-order operators on relations, akin to the <jats:italic>fold<\/jats:italic> operators found in functional programming languages. In the present context, a data type is modelled as an initial <jats:italic>F<\/jats:italic>-algebra, where <jats:italic>F<\/jats:italic> is an endofunctor on the topos under consideration. The mediating arrows from this initial <jats:italic>F<\/jats:italic>-algebra to other <jats:italic>F<\/jats:italic>-algebras are instances of fold \u2013 but only for total functions. For a <jats:italic>regular<\/jats:italic> category \u03b5, it is possible to construct a category of relations Rel(\u03b5). When a functor between regular categories is a so-called <jats:italic>relator<\/jats:italic>, it can be extended (in some canonical way) to a functor between the corresponding categories of relations. Applied to an endofunctor on a topos, this process of extending functors preserves initial algebras, and hence fold can be generalised from functions to relations.<\/jats:p><jats:p>It is well-known that the use of dynamic programming is governed by the <jats:italic>principle of optimality<\/jats:italic>. Roughly, the principle of optimality says that an optimal solution is composed of optimal solutions to subproblems. In a first attempt, we formalise the principle of optimality as a distributivity condition. This distributivity condition is elegant, but difficult to check in practice. The difficulty arises because we consider minimum elements with respect to a preorder, and therefore minimum elements are not unique. Assuming that we are working in a Boolean topos, it can be proved that monotonicity implies distributivity, and this monotonicity condition is easy to verify in practice.<\/jats:p>","DOI":"10.1017\/s0960129500000360","type":"journal-article","created":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T09:01:18Z","timestamp":1236157278000},"page":"33-69","source":"Crossref","is-referenced-by-count":5,"title":["Categories, relations and dynamic programming"],"prefix":"10.1017","volume":"4","author":[{"given":"Oege De","family":"Moor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,3,4]]},"reference":[{"key":"S0960129500000360_ref020","unstructured":"Cockett R. (1991) Personal Communication."},{"key":"S0960129500000360_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(89)90036-1"},{"key":"S0960129500000360_ref019","unstructured":"Cockett R. and Fukushima T. (1991) Draft: About Charity, Dept. of Computer Science, University of Calgary, Calgary, Alberta, Canada. Available via anonymous ftp from cpsc.ucalgary.ca."},{"key":"S0960129500000360_ref016","first-page":"47","article-title":"A 2-Categorical Approach to Geometric Morphisms I","volume":"32","author":"Carboni","year":"1991","journal-title":"Cahiers de Topologie et Geometrie Differentielle Categoriques"},{"key":"S0960129500000360_ref025","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014657"},{"key":"S0960129500000360_ref013","first-page":"287","volume-title":"Research Topics in Functional Programming","author":"Bird","year":"1990"},{"key":"S0960129500000360_ref015","unstructured":"Carboni A. and Rosolini G. (1991) The Free Regular Category on a Left Exact One. (In preparation)"},{"key":"S0960129500000360_ref005","unstructured":"Bird R. S. and de Moor O. (1991) Inductive Solutions to Optimisation Problems. (Draft)"},{"key":"S0960129500000360_ref036","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(86)90147-2"},{"key":"S0960129500000360_ref002","doi-asserted-by":"publisher","DOI":"10.1137\/0219066"},{"key":"S0960129500000360_ref040","first-page":"247","volume-title":"Programming Concepts and Methods","author":"Jeuring","year":"1990"},{"key":"S0960129500000360_ref066","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"S0960129500000360_ref058","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(90)90025-9"},{"key":"S0960129500000360_ref062","doi-asserted-by":"publisher","DOI":"10.1109\/32.58788"},{"key":"S0960129500000360_ref017","unstructured":"Casimir R. J. (1980) Program Inversion. Technical Report AIV-80\u201310, Vakgroep AIV, Erasmus Universiteit, Postbus 1730, 3000 DR Rotterdam, The Netherlands."},{"key":"S0960129500000360_ref014","volume-title":"Notes on Pure Mathematics","volume":"9","author":"Brook","year":"1977"},{"key":"S0960129500000360_ref030","volume-title":"Mathematical Library","volume":"39","author":"Freyd","year":"1990"},{"key":"S0960129500000360_ref051","doi-asserted-by":"publisher","DOI":"10.1038\/218019a0"},{"key":"S0960129500000360_ref009","doi-asserted-by":"publisher","DOI":"10.1145\/356827.356831"},{"key":"S0960129500000360_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(90)90042-C"},{"key":"S0960129500000360_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0083084"},{"key":"S0960129500000360_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90101-1"},{"key":"S0960129500000360_ref007","volume-title":"Introduction to Functional Programming","author":"Bird","year":"1988"},{"key":"S0960129500000360_ref028","volume-title":"Functional Programming","author":"Field","year":"1988"},{"key":"S0960129500000360_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(86)90023-7"},{"key":"S0960129500000360_ref065","first-page":"1","volume-title":"Springer-Verlag Lecture Notes in Computer Science","volume":"201","author":"Turner","year":"1985"},{"key":"S0960129500000360_ref012","first-page":"151","volume-title":"NATO ASI Series F","volume":"55","author":"Bird","year":"1989"},{"key":"S0960129500000360_ref011","first-page":"3","volume-title":"NATO AS I Series F","volume":"36","author":"Bird","year":"1987"},{"key":"S0960129500000360_ref001","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"S0960129500000360_ref038","doi-asserted-by":"publisher","DOI":"10.1137\/0216043"},{"key":"S0960129500000360_ref050","volume-title":"Data Structures and Algorithms","author":"Mehlhorn","year":"1984"},{"key":"S0960129500000360_ref056","volume-title":"IFIP WG 10.1 workshop on Concepts and Characteristics of Declarative Systems, Budapest 1988","author":"Sheeran","year":"1989"},{"key":"S0960129500000360_ref006","doi-asserted-by":"crossref","unstructured":"Bird R. S. and de Moor O. (1992) List Partitions. Formal Aspects of Computing. (To appear)","DOI":"10.1007\/BF01211316"},{"key":"S0960129500000360_ref046","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90036-1"},{"key":"S0960129500000360_ref035","doi-asserted-by":"publisher","DOI":"10.1137\/0606032"},{"key":"S0960129500000360_ref055","volume-title":"Algorithms","author":"Sedgewick","year":"1983"},{"key":"S0960129500000360_ref042","unstructured":"Jones G. (1990) Designing Circuits by Calculation. Technical Report PRG-TR-10\u201390, Programming Research Group, 11 Keble Road, Oxford OX1 3QD, England."},{"key":"S0960129500000360_ref022","unstructured":"de Moor O. (1992a) Categories, Relations and Dynamic Programming, D.Phil, thesis, Technical Monograph PRG-98, Computing Laboratory, Oxford."},{"key":"S0960129500000360_ref060","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(87)90034-7"},{"key":"S0960129500000360_ref023","doi-asserted-by":"crossref","unstructured":"de Moor O. (1992b) Inductive Data Types for Predicate Transformers. Information Processing Letters. (To appear)","DOI":"10.1016\/0020-0190(92)90001-C"},{"key":"S0960129500000360_ref026","volume-title":"Introduction to Operations Research","author":"Ecker","year":"1988"},{"key":"S0960129500000360_ref024","volume-title":"Dynamic Programming - Models and Applications","author":"Denardo","year":"1982"},{"key":"S0960129500000360_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90670-5"},{"key":"S0960129500000360_ref044","first-page":"1119","article-title":"Breaking Paragraphs into Lines","volume":"11","author":"Knuth","year":"1981","journal-title":"Software: Practice and Experience"},{"key":"S0960129500000360_ref032","unstructured":"Gardiner P. H. B. , Martin C. E. and de Moor O. (1992) Factoring Predicate Transformers in a Topos. (Draft)"},{"key":"S0960129500000360_ref033","unstructured":"Goguen J. A. and Winkler T. (1988) Introducing OBJ3. Technical Report SRI-CSL-88\u20139, Computing Science Laboratory, SRI International, 333 Ravenswood Ave., Menlo Park, CA 94025, USA."},{"key":"S0960129500000360_ref034","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185679"},{"key":"S0960129500000360_ref048","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4962-7"},{"key":"S0960129500000360_ref037","doi-asserted-by":"publisher","DOI":"10.1145\/58562.59304"},{"key":"S0960129500000360_ref039","first-page":"130","volume-title":"Springer-Verlag Lecture Notes in Computer Science","volume":"201","author":"Hughes","year":"1985"},{"key":"S0960129500000360_ref004","volume-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"key":"S0960129500000360_ref041","volume-title":"Topos Theory","author":"Johnstone","year":"1977"},{"key":"S0960129500000360_ref052","volume-title":"Programming from Specifications","author":"Morgan","year":"1990"},{"key":"S0960129500000360_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(91)90022-P"},{"key":"S0960129500000360_ref043","doi-asserted-by":"publisher","DOI":"10.1137\/0115060"},{"key":"S0960129500000360_ref045","doi-asserted-by":"publisher","DOI":"10.1007\/BF01752392"},{"key":"S0960129500000360_ref047","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(90)90023-7"},{"key":"S0960129500000360_ref049","first-page":"3","volume-title":"Mathematics and Computer Science","author":"Meertens","year":"1987"},{"key":"S0960129500000360_ref053","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90007-5"},{"key":"S0960129500000360_ref021","doi-asserted-by":"publisher","DOI":"10.1145\/567752.567766"},{"key":"S0960129500000360_ref054","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90147-8"},{"key":"S0960129500000360_ref057","first-page":"380","volume-title":"Springer-Verlag Lecture Notes in Computer Science","volume":"408","author":"Sheeran","year":"1990"},{"key":"S0960129500000360_ref059","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90083-9"},{"key":"S0960129500000360_ref061","unstructured":"Smith D. R. (1988) Structure and Design of Global Search Algorithms. Report KES.U.87.12, Kestrel Institute, 1801 Page Mill Road, Palo Alto, CA 94304. Acta Informatica. (To appear)"},{"key":"S0960129500000360_ref063","volume-title":"Proc. of the IFIP TC2 Working Conference on Constructing Programs from Specifications","author":"Smith","year":"1991"},{"key":"S0960129500000360_ref064","doi-asserted-by":"publisher","DOI":"10.1007\/BF00939252"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129500000360","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T19:03:12Z","timestamp":1557946992000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129500000360\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["S0960129500000360"],"URL":"https:\/\/doi.org\/10.1017\/s0960129500000360","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}