TY - GEN
T1 - Coalgebraic weak bisimulation from recursive equations over monads
AU - Goncharov, Sergey
AU - Pattinson, Dirk
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84904208383&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-43951-7_17
DO - 10.1007/978-3-662-43951-7_17
M3 - Conference contribution
SN - 9783662439500
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 196
EP - 207
BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PB - Springer Verlag
T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
Y2 - 8 July 2014 through 11 July 2014
ER -