Coalgebraic Weak Bisimulation from Recursive Equations over Monads

DOI10.1007/978-3-662-43951-7_17MaRDI QIDQ5167838zbMATH OpenOpenAlexFDO

Authors Dirk Pattinson, S. S. Goncharov

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.1215

Mathematics Subject Classification ID

Categories of machines, automata (18B20) Eilenberg-Moore and Kleisli constructions for monads (18C20) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

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.

Recommendations

• Weak bisimulation for coalgebras over order enriched monads
• Towards weak bisimulation for coalgebras
• Weak Bisimulations for the Giry Monad (Extended Abstract)
• Weak bisimulations for the Giry monad
• A syntactical approach to weak (bi-)simulation for coalgebras
• Coalgebraic weak bisimulation for action-type systems
• Weak bisimulations for coalgebras over ordered functors
• Weak bisimulation for action-type coalgebras (extended abstract)
• Weak bisimilarity coalgebraically
• Coalgebraic bisimulation-up-to

Cited in

(15)

• Weak bisimulation for action-type coalgebras (extended abstract)
• An exercise on transition systems
• Weak bisimilarity coalgebraically
• Weak bisimulations for coalgebras over ordered functors
• Weak bisimulation for coalgebras over order enriched monads
• Behavioural equivalences for timed systems
• Quotienting the delay monad by weak bisimilarity
• On path-based coalgebras and weak notions of bisimulation
• Coalgebraic weak bisimulation for action-type systems
• A coalgebraic take on regular and \(\omega\)-regular behaviour for systems with internal moves
• A coalgebraic take on regular and -regular behaviours
• A general account of coinduction up-to
• Traces via strategies in two-player games
• Killing epsilons with a dagger: a coalgebraic study of systems with algebraic label structure
• Behavioural equivalences for coalgebras with unobservable moves

This page was built for publication: Coalgebraic Weak Bisimulation from Recursive Equations over Monads

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167838)