Bisimulation Cuts For Structuring Markov Transition Systems

Article type: Research Article

Authors: Doberkat, Ernst-Erich^*

Affiliations: Math++Software, Bochum, Germany. [email protected]

Correspondence: [*] Most of this work was done while the author held the Chair for Software Technology at the Technische Universität Dortmund. It was funded in part by Deutsche Forschungsgemeinschaft, grant DO 263/12-1, Koalgebraische Eigenschaften stochastischer Relationen. Address for correspondence: Math++Software, Bochum, Germany.

Abstract: In Universal Algebra the structure of congruences for algebraic systems is fairly well investigated, and the relationship to the structure of the underlying system proper is well known. We propose a first step into this direction for studying the structure of congruences for stochastic relations. A Galois connection to a certain class of Boolean σ-algebras is exploited, atoms and antiatoms are identified, and it is show that a σ-basis exists. These constructions are applied to the problem of finding bisimulation cuts of a congruence. It cuts the relation through a span of morphisms with a minimum of joint events.

DOI: 10.3233/FI-2016-1452

Journal: Fundamenta Informaticae, vol. 149, no. 4, pp. 363-383, 2016