On a representation of measurable automaton transformations by stochastic automata. (English) Zbl 0365.94076

Let \((X,\mathcal A)\) be a measurable, \((Y,\mathcal B)\) be a Borel space, and denote by \((X^*,\mathcal A^*)\) the direct sum of \(((X^n,\mathcal A^n))_{n\geq 0}\). If \(K\) is a transition probability from \((X^*,\mathcal A^*)\) to \((Y^*,\mathcal B^*)\), \(K\) is said to be a stochastic transformation iff for every \(v\in X^*\), \(K(v)(Y^{| v|}) = 1\), and if for every \(x\in X\), \(B\in\mathcal B^*\), \(K(vx)(B\times Y) = K(v)(B)\) holds \((| v|\) denoting the length of \(v)\). By means of a disintegration theorem due to D. Rhenius [Markoffsche Entscheidungsprozesse mit unvollständiger Information und Anwendungen in der Lerntheorie. Thesis, Hamburg (1971), see also Ann. Stat. 2, 1327–1334 (1974; Zbl 0294.49007)] it is shown that \(K\) is a stochastic transformation iff it is the behavior of an initial stochastic automaton. If \(Y\) is \(\sigma\)-compact and Polish, an automaton transformation \(R\) (i.e. the behavior of an initial complete nondeterministic automaton, cf. A. Schmitt [Computing 4, 56–74 (1969; Zbl 0213.02203)]) is said to be measurable iff \(R\) is closed-valued, and if \(X^*\ni v\rightarrow R(v)\subset Y^*\) is (weakly) measurable [C. J.Himmelberg, Fundam. Math, 87, 53–72 (1975; Zbl 0296.28003)].
The main result of this paper is that \(R\) is measurable iff there exists a stochastic transformation \(K\) such that \(\forall v\in X^*\) : \(R(v)=\text{supp}(K(v))\), \(\text{supp}\) denoting support. This is shown by means of measurable selections [D. H. Wagner, SIAM J. Control Optim. 15, 859–903 (1977; Zbl 0407.28006)] for the weakly measurable relation that assigns to every \(v\) the set of all probabilities which have their support in \(R(v)\). This result implies that a closed-valued relation \(F\) from \(X\) to \(Y\) is measurable iff there exists a transition probability from \((X,\mathcal A)\) to \((Y,\mathcal B)\) such that \(F(x) = \text{supp}(K(x))\) holds for every \(x\in X\).


68Q45 Formal languages and automata
28A20 Measurable and nonmeasurable functions, sequences of measurable functions, modes of convergence
Full Text: DOI


[1] Billingsley, P.: Convergence of probability measures. (1968) · Zbl 0172.21201
[2] Bourbaki, N.: ”General topology,” part 2. (1966) · Zbl 0145.19302
[3] Brauer, W.: Zu den grundlagen einer theorie topologischer sequentieller systeme und automaten. Report 31 (1970) · Zbl 0216.56503
[4] Claus, V.: Stochastische automaten. (1971) · Zbl 0226.94046
[5] Doberkat, E. -E: Optimal strategies in measurable learning systems on metric spaces. J. appl. Probability 14, 795-805 (1977) · Zbl 0385.68069
[6] Dunford, N.; Schwartz, J. T.: ”Linear operators,” part I. (1957) · Zbl 0128.34803
[7] Himmelberg, C. J.: Measurable relations. Fund. math. 87, 53-72 (1975) · Zbl 0296.28003
[8] Himmelberg, C. J.; Van Vleck, F. S.: Multifunctions with values in a space of probability measures. J. math. Anal. appl. 50, 108-112 (1975) · Zbl 0299.54009
[9] Hinderer, K.: Foundations of non-stationary dynamic programming with discrete time parameter. Lecture notes in operations research and mathematical systems no. 33 (1970) · Zbl 0202.18401
[10] Menzel, W.: An extension of the theory of learning systems. Acta informatica 2, 357-381 (1973) · Zbl 0261.68043
[11] Parthasarathy, K. R.: Probability measures on metric spaces. (1967) · Zbl 0153.19101
[12] Rhenius, D.: Markoffsche entscheidungsmodelle mit unvollständiger information und anwendungen in der lerntheorie. Doctoral dissertation (1971)
[13] Rieder, U.: Bayesian dynamic programming. Advances in appl. Probability 7, 330-348 (1975) · Zbl 0316.90081
[14] Rockafellar, R. T.: Integral functionals, normal integrands, and measurable selections. Lecture notes in mathematics no. 543, 157-207 (1976) · Zbl 0374.49001
[15] Schmitt, A.: Zur theorie der nichtdeterministischen und unvollständigen automaten. Computing 4, 56-74 (1969) · Zbl 0213.02203
[16] Starke, P. H.: Theorie stochastischer automaten. Elektron. informationsverarbeit. Kybernetik 1, 71-98 (1965) · Zbl 0149.01003
[17] Wagner, D. H.: Survey of measurable selection theorems. SIAM J. Control optimization 15, 859-903 (1977) · Zbl 0407.28006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.