Stochastic coalgebraic logic
type: Item
instance of: scholarly article
title: Stochastic coalgebraic logic
zbMATH Open document ID: 1207.03039
DOI: 10.1007/978-3-642-02995-0
author: Ernst-Erich Doberkat
published in: Monographs in Theoretical Computer Science. An EATCS Series
publication date: 2010-01-14T00:00:00Z
review text: Stochastic logics over measurable spaces, specifically analytic spaces, originally go back to \textit{J. Desharnais, A. Edalat} and \textit{P. Panangaden}, [``Bisimulation for labelled Markov processes'', Inf. Comput. 179, No.~2, 163--193 (2002; Zbl 1096.68103)]. The main result on stochastic logics is that they characterize bisimilarity of probabilistic systems. The present monograph lifts these results to the level of generality of coalgebras over analytic spaces, in analogy to the set-based case developed by \textit{D. Pattinson} [``Expressive logics for coalgebras via terminal sequence induction'', Notre Dame J. Formal Logic 45, No.~1, 19--33 (2004; Zbl 1088.03031)] and \textit{L. Schröder} [``Expressivity of coalgebraic modal logic: the limits and beyond'', Theor. Comput. Sci. 390, No.~2--3, 230--247 (2008; Zbl 1132.03008)]. Here, a coalgebra is a system of the shape \(\xi:X\to FX\) where \(F\) is some endofunctor on the base category, i.e., an assignment of a structured collection \(\xi(x)\) of successors to each state \(x\), where the nature of the structured collection is determined by the functor \(F\), which may, e.g., encapsulate \(n\)-ary relations for arbitrary finite or infinite \(n\). (In the set-based case, \(F\) often encodes also much more complex behaviour; such examples are not yet developed in the measurable case.) The basic example in the stochastic setting is for \(F\) to be the subprobabilities functor, so that coalgebras for \(F\) are stochastic transition systems. The monograph is concerned almost entirely with the question of when two basic equivalences on stochastic (coalgebraic) models coincide, namely logical equivalence (indistinguishability under the formulas of a given logic), behavioural equivalence (identification under a \textit{cospan}, i.e., two morphisms into a common target model), and bisimilarity (identification via a \textit{span}, i.e., two model morphisms from a common source). It is well known (and is formally discussed …
reviewed by: Lutz Schröder
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 03B45
Mathematics Subject Classification ID: 60J05
Mathematics Subject Classification ID: 60J25
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 68Q87
Mathematics Subject Classification ID: 03-02
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 5657968
zbMATH Keywords: modal logic
zbMATH Keywords: Markov chains
zbMATH Keywords: stochastic relations
zbMATH Keywords: bisimilarity
zbMATH Keywords: behavioural equivalence
zbMATH Keywords: logical equivalence
zbMATH Keywords: coalgebraic logic
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-3-642-02995-0
OpenAlex ID: W4212880253
description: scientific article; zbMATH DE number 5657968