On probabilistic automata in deterministic environment

Article type: Research Article

Authors: Gould, Jerren^a | Wegman, Edward J.^b

Affiliations: [a] Clermont Graduate School | [b] University of North Carolina at Chapel Hill and University of Manchester

Abstract: We establish the basic notion of automata in environments and solve some of the basic problems in the general theory of automata in deterministic environment (ADE). ADE are, in general, stronger than probabilistic automata. In an effort to find when an ADE and a PA have the same capability, we introduce the concept of simulation of an ADE by a PA. Every ADE with a finite environment set can be simulated by a PA (Theorem 1). There are sets which cannot be defined by PA but can be defined by ADE with finite environment sets and, hence, can be simulated by a PA. ADE for which the environment can be reduced to a finite set can be simulated by a PA (Theorem 2). The set of stochastic matrices is a semi-group. We investigate the case where the environment set is also a semi-group and the transition function is a homomorphism between the semi-groups. If the semi-group environment set can be generated by a finite set, then the ADE can be simulated by a PA (Theorem 3). The continuous time PA of Knast [2] is seen to be a special case of the ADE.

Keywords: automaton, probabilistic automaton, automaton in environments, probabilistic tables, cut-point, probabilistic cut-point event, environment

DOI: 10.3233/FI-1980-3102

Journal: Fundamenta Informaticae, vol. 3, no. 1, pp. 1-13, 1980