Solvable classes of discrete dynamic programming

As finite state models to represent a discrete optimization problem given in the form of an r-ddp (recursive discrete decision process), three subclasses of r-msdp (recursive monotone sequential decision process) are introduced in this paper. They all have a feature that the functional equations of dynamic programming hold and there exists an algorithm (in the sense of the theory of computation) to obtain the set of optimal policies. (In this sense, we may call them solvable classes of discrete dynamic programming.) Besides the algorithms for obtaining optimal policies, two types of representations are extensively studied for each class of r-msdp's. Other related decision problems are also discussed. It turns out that some of them are solvable while the rest of them are unsolvable.