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
Get full access to this article
View all access options for this article.