Stochastic non-determinism and effectivity functions

ERNST-ERICH DOBERKAT; PEDRO SÁNCHEZ TERRAF

JOURNAL OF LOGIC AND COMPUTATION

OXFORD UNIV PRESS

Lugar: Oxford; Año: 2015 vol. 27 p. 357 - 394

0955-792X

This article investigates stochastic non-determinism on continuous state spaces by relating non-deterministic kernels and stochastic effectivity functions to each other. Non-deterministic kernels are functions assigning each state a set of subprobability measures, and effectivity functions assign to each state an upper-closed set of subsets of measures. Both concepts are generalizations of Markov kernels used for defining two different models: non-deterministic labelled Markov processes and stochastic game models, respectively. We show that an effectivity function that maps into principal filters is given by an image-countable non-deterministic kernel, and that image-finite kernels give rise to effectivity functions. We define state bisimilarity for the latter, considering its connection to morphisms. We provide a logical characterization of bisimilarity in the finitary case. A generalization of congruences (event bisimulations) to effectivity functions and its relation to the categorical presentation of bisimulation are also studied.