Design and Analysis of an Optimal Control Algorithm for the Output of a Stochastic Automaton

Article type: Research Article

Authors: Doberkat, Ernst E.

Affiliations: Clarkson College of Technology, Potsdam, New York 13676

Abstract: Given the input-output behavior of a stochastic automaton and a map which compares output words, optimal controls are introduced, and an explicit formula for such a control is derived by means of linear programming techniques. The second part of the paper deals with the situation in which an input and an output word are given and the probability with which the optimal control puts out the word is requested. An algorithm for computing this probability is presented and analysed with respect to its behavior in the worst and in the average case. The latter analysis develops some new techniques, which are necessary since an uncountable variety of possible inputs has to be considered. These techniques come mainly from real analysis, in particular from measure theory.

Keywords: Stochastic automata, optimal control, linear programming, analysis of algorithms, average complexity

DOI: 10.3233/FI-1982-5104

Journal: Fundamenta Informaticae, vol. 5, no. 1, pp. 35-75, 1982