Design and Analysis of an Optimal Control Algorithm for the Output of a Stochastic Automaton
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 this paper deals with the situation that 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 as well as 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.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten