Coalgebraic weak bisimulation from recursive equations over monads

Sergey Goncharov, Dirk Pattinson

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    11 Citations (Scopus)

    Abstract

    Strong bisimulation for labelled transition systems is one of the most fundamental equivalences in process algebra, and has been generalised to numerous classes of systems that exhibit richer transition behaviour. Nearly all of the ensuing notions are instances of the more general notion of coalgebraic bisimulation. Weak bisimulation, however, has so far been much less amenable to a coalgebraic treatment. Here we attempt to close this gap by giving a coalgebraic treatment of (parametrized) weak equivalences, including weak bisimulation. Our analysis requires that the functor defining the transition type of the system is based on a suitable order-enriched monad, which allows us to capture weak equivalences by least fixpoints of recursive equations. Our notion is in agreement with existing notions of weak bisimulations for labelled transition systems, probabilistic and weighted systems, and simple Segala systems.

    Original languageEnglish
    Title of host publicationAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
    PublisherSpringer Verlag
    Pages196-207
    Number of pages12
    EditionPART 2
    ISBN (Print)9783662439500
    DOIs
    Publication statusPublished - 2014
    Event41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark
    Duration: 8 Jul 201411 Jul 2014

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    NumberPART 2
    Volume8573 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
    Country/TerritoryDenmark
    CityCopenhagen
    Period8/07/1411/07/14

    Fingerprint

    Dive into the research topics of 'Coalgebraic weak bisimulation from recursive equations over monads'. Together they form a unique fingerprint.

    Cite this