Finite-State Processes and Dynamic Programming

This paper develops a formalism within which the application of dynamic programming to discrete, deterministic problems is rigorously studied. The two central concepts underlying this development are discrete decision process and sequential decision process. Discrete decision processes provide a convenient means of problem statement, while monotone sequential decision processes (which are finite automata with a certain cost structure superimposed) correspond naturally to dynamic programming algorithms. The representations of discrete decision processes by monotone sequential decision processes are characterized, and this characterization is used in the deviation of dynamic programming algorithms for a variety of problems.