Paolo Baldan ; Filippo Bonchi ; Henning Kerstan ; Barbara König - Coalgebraic Behavioral Metrics

lmcs:4715 - Logical Methods in Computer Science, September 14, 2018, Volume 14, Issue 3 -
Coalgebraic Behavioral Metrics

Authors: Paolo Baldan ; Filippo Bonchi ; Henning Kerstan ; Barbara König

    We study different behavioral metrics, such as those arising from both branching and linear-time semantics, in a coalgebraic setting. Given a coalgebra $\alpha\colon X \to HX$ for a functor $H \colon \mathrm{Set}\to \mathrm{Set}$, we define a framework for deriving pseudometrics on $X$ which measure the behavioral distance of states. A crucial step is the lifting of the functor $H$ on $\mathrm{Set}$ to a functor $\overline{H}$ on the category $\mathrm{PMet}$ of pseudometric spaces. We present two different approaches which can be viewed as generalizations of the Kantorovich and Wasserstein pseudometrics for probability measures. We show that the pseudometrics provided by the two approaches coincide on several natural examples, but in general they differ. If $H$ has a final coalgebra, every lifting $\overline{H}$ yields in a canonical way a behavioral distance which is usually branching-time, i.e., it generalizes bisimilarity. In order to model linear-time metrics (generalizing trace equivalences), we show sufficient conditions for lifting distributive laws and monads. These results enable us to employ the generalized powerset construction.

    Volume: Volume 14, Issue 3
    Published on: September 14, 2018
    Accepted on: July 31, 2018
    Submitted on: July 26, 2018
    Keywords: Computer Science - Logic in Computer Science
      Source : OpenAIRE Graph
    • Reliable and Privacy-Aware Software Systems via Bisimulation Metrics; Funder: French National Research Agency (ANR); Code: ANR-16-CE25-0011

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsCitedBy ARXIV 2005.07509
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.concur.2020.28
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2005.07509
    • 10.4230/lipics.concur.2020.28
    • 10.48550/arxiv.2005.07509
    • 2005.07509
    Monads and Quantitative Equational Theories for Nondeterminism and Probability
    Mio, Matteo ; Vignudelli, Valeria ;

    4 Documents citing this article

    Consultation statistics

    This page has been seen 1078 times.
    This article's PDF has been downloaded 383 times.