Equivalence Relations in Classes of Stochastic Automata

Article type: Research Article

Authors: Janicki, Sławomir

Affiliations: Technical University of Lublin

Abstract: Bartoszyński raised and investigated problems of extensions and shrinkages of the Markov chain type stochastic automata (Some remarks on extensions of stochastic automata, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 18(1970), 551–556). By such an automaton we mean an ordered triple ⟨T, α, A⟩, where T denotes a finite non-empty set, α is a function from T to [0, 1] with ∑t∈Tα(t)=1, and A is a function T×T → [0, 1] with ∑t∈TA(s,t)=1 for every s ∈ T. If an extension (shrinkage) of two automata exists, then we say that they satisfy the relation Re(Rs). The aim of this paper is to consider some classes of automate with the same set T in which the relations Re and Rs are equivalence relations. We consider also some other relations in the class of stochastic automata. Moreover, in the first part we deal with extensions and shrinkages of probability measures.

Keywords: stochastic automaton, extension of automata, shrinkage of automata, concordance of automata

DOI: 10.3233/FI-1985-8103

Journal: Fundamenta Informaticae, vol. 8, no. 1, pp. 27-54, 1985