Dynamic Programming as Graph Searching: An Algebraic Approach

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic Programming as Graph Searching: An Algebraic Approach

Full text

Pdf (836 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 4 (October 1981) table of contents

Pages: 737 - 751

Year of Publication: 1981

ISSN:0004-5411

Authors

Stefania Gnesi	Istituto di Scienze dell'Informazione, University of Pisa, C/so Italia, 40, I-56100 Pisa, Italy
Ugo Montanari	Istituto di Scienze dell'Informazione, University of Pisa, C/so Italia, 40, I-56100 Pisa, Italy
Alberto Martelli	Istituto dt Elaborazione della Informazione del C N R, Via S Maria, 46, I-56100 Pisa, Italy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 65, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322276.322285 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ARNOLD, A., AND NIVAT, M. Nondetermmlstic recursive program schemes. In Fundamentals of Computauon Theory 1977, Lecture Notes in Computer Science 56, M. Karpinsh, Ed., Springer Verlag, Berlin, Heidelberg, 1977, pp. 12-21.
	2	Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
	3	BLIKLE, A.Equational languages. Inf. Control 21 (1972), 134-147
	4	J. A. Goguen , J. W. Thatcher , E. G. Wagner , J. B. Wright, Initial Algebra Semantics and Continuous Algebras, Journal of the ACM (JACM), v.24 n.1, p.68-95, Jan. 1977 [doi>10.1145/321992.321997]
	5	HART, P., NILSSON, N., AND RAPHAEL, B A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Scl. Cybern. SSC-4, 2 (July 1968), 100-107.
	6	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	7	IBARAKI, T.Classes of discrete optimizaUon problems and their decision problems. 3'. Comput. Syst. Scl. 8 (1974), 84-116.
	8	IBARAKI, TOn the opumahty of algorithms for finite state sequential deosion processes. J Math. Anal Appl 53, 3 (March 1976), 618-643
	9	Donald Bruce Johnson, Algorithms for shortest paths., 1973
	10	KARP, R.M, AND HELD, M. Finite-state processes and dynamic programming SIAM ~ Appl Math. 15 (1967), 693-718
	11	KNUTH, D.E Opumum binary search trees Acta Inf 1 (1971), 14-25
	12	KNUTH, D E A generahzauon of Dijkstra's algorithm Inf Proc Lett 6 (Feb 1977), 1-4
	13	MARTELLI, A., AND MONTANARI, U Additive AND/OR graphs Proc 3rd Int. Joint Conf on Artlfioal lntelhgence, Stanford, Cahf, 1973, pp 1-11
	14	MARTELLI, A, AND MONTANARI, U Programmaz~one dmamlca e punto fisso Proc Convegno dl Informatics Teonca, Mantova, Italy, Nov 1974, pp 1-19
	15	MARTELLI, A, AND MONTANARI, U On the foundauons of dynamic programming In Topws m Combinatorial Optlmtzanon, S. Rmaldt, Ed., Springer Verlag, Vienna, New York, 1975, pp 145-163
	16	MARTELLI, A, AND MONTANARI, U From dynamic programming to search algorithms with functlonal costs Proc 4th Int. Joint Conf on ArUficlal lntelhgence, Tblllsl, USSR, Sept. 1975, pp 345- 350
	17	Alberto Martelli , Ugo Montanari, Optimizing decision trees through heuristically guided search, Communications of the ACM, v.21 n.12, p.1025-1039, Dec. 1978 [doi>10.1145/359657.359664]
	18	Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
	19	Helmut Schumacher , Kenneth C. Sevcik, The synthetic approach to decision table conversion, Communications of the ACM, v.19 n.6, p.343-351, June 1976 [doi>10.1145/360238.360245]
	20	TARSKI, A A lattlce-theoreUcal fixpomt theorem and its applications Pactfic ~ Math 5 (1955), 285- 309.
	21	THATCHER, J W Tree automata An informal survey In Currents m the Theory of Computing, A V Aho, Ed, Prenuce Hall, Englewood Cliffs, N.J, 1973, pp 143-172
	22	WHITE, D J Dynamic Programming Oliver & Boyd, Edinburgh, 1969

CITED BY 2

	Stefano Bistarelli , Ugo Montanari , Francesca Rossi, Semiring-based constraint satisfaction and optimization, Journal of the ACM (JACM), v.44 n.2, p.201-236, March 1997
	Jurek Czyzowicz , Wojciech Fraczak , Mohammadreza Yazdani, Computing the throughput of Concatenation State Machines, Journal of Discrete Algorithms, v.6 n.1, p.28-36, March, 2008