On stability of probabilistic automata in environments¹

Article type: Research Article

Authors: Gould, Jerren

Affiliations: Department of Mathematics, Claremont Graduate School

Note: [1] This work arises from the author’s doctoral dissertation and was supported in part by the Air Force Office of Scientific Research under Grant No. AFOSR-75-2840.

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 (A, e, λ), the set of tapes accepted by 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.

Keywords: Automaton, probabilistic automaton, automaton in environment, stability, a-stable, s-stable

DOI: 10.3233/FI-1980-3202

Journal: Fundamenta Informaticae, vol. 3, no. 2, pp. 117-134, 1980