On stability of probabilistic automata in environments 1

Abstract

Flachs [1], Rabin [7], and Paz [6] have considered topics in the stability of probabilistic automata. Here we extend these results to the more general forms, automata in deterministic environments (ADE). We shall be concerned with two types of stability problems that arise from small perturbations of the environment configurations for an ADE. By consideration of the asymptotic properties of long products of stochastic matrices whose entries are subject to small perturbations concomitant to the environment configuration perturbations, we arrive at sufficient conditions for the state distribution function to be stable (s-stability). In its acceptor formulation the behavior of an ADE is characterized by the sets T ( $\mathcal{A}$ , e, λ), the set of tapes accepted by $\mathcal{A}$ with environment sequence e and cut-point λ. Sufficient conditions are given for tape-acceptance stability (a-stability) in terms of s-stability and in terms that do not require s-stability. These stability results are pointwise results that give the size of the perturbation of the environment configuration to avoid instability.