Coalgebraic Weak Bisimulation from Recursive Equations over Monads

Goncharov S, Pattinson D (2014)

Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2014

Publisher: Springer

Edited Volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Series: Lecture Notes in Computer Science

City/Town: Berlin/Heidelberg

Book Volume: 8573

Pages Range: 196-207

Conference Proceedings Title: Proc. 41st International Colloquium on Automata, Languages, and Programming

Event location: Kopenhagen

URI: http://www8.cs.fau.de/publications

DOI: 10.1007/978-3-662-43951-7_17

Open Access Link: http://arxiv.org/pdf/1404.1215v2.pdf

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. © 2014 Springer-Verlag.

Authors with CRIS profile

Sergey Goncharov Lehrstuhl für Informatik 8 (Theoretische Informatik)

Involved external institutions

Australian National University (ANU) AU Australia (AU)

How to cite

APA:

Goncharov, S., & Pattinson, D. (2014). Coalgebraic Weak Bisimulation from Recursive Equations over Monads. In Proc. 41st International Colloquium on Automata, Languages, and Programming (pp. 196-207). Kopenhagen: Berlin/Heidelberg: Springer.

MLA:

Goncharov, Sergey, and Dirk Pattinson. "Coalgebraic Weak Bisimulation from Recursive Equations over Monads." Proceedings of the ICALP 2014, Kopenhagen Berlin/Heidelberg: Springer, 2014. 196-207.

BibTeX: Download