Document Open Access Logo

On Path-Based Coalgebras and Weak Notions of Bisimulation

Authors Harsh Beohar, Sebastian Küpper

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2017.6.pdf
  • Filesize: 0.57 MB
  • 17 pages

Document Identifiers

Author Details

Harsh Beohar
Sebastian Küpper

Cite As Get BibTex

Harsh Beohar and Sebastian Küpper. On Path-Based Coalgebras and Weak Notions of Bisimulation. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CALCO.2017.6

Abstract

It is well known that the theory of coalgebras provides an abstract definition of behavioural equivalence that coincides with strong bisimulation across a wide variety of state-based systems. Unfortunately, the theory in the presence of so-called silent actions is not yet fully developed. In this paper, we give a coalgebraic characterisation of branching (delay) bisimulation in the context of labelled transition systems (fully probabilistic systems). It is shown that recording executions (up to a notion of stuttering), rather than the set of successor states, from a state is sufficient to characterise the respected bisimulation relations in both cases.

Subject Classification

Keywords
  • Paths
  • Executions
  • Branching bisimulation
  • Coalgebras

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Adámek, F. Bonchi, M. Hülsbusch, B. König, S. Milius, and A. Silva. A coalgebraic perspective on minimization and determinization. In Proc. of FOSSACS '12, pages 58-73. Springer, 2012. LNCS/ARCoSS 7213. Google Scholar
  2. P. Alexandroff. Diskrete räume. Rec. Math. N.S., 2(44)(3):501-519, 1937. Google Scholar
  3. M. Alvarez-Manilla. Extension of valuations on locally compact sober spaces. Topology and its Applications, 124(3):397 - 433, 2002. Google Scholar
  4. C. Baier and H. Hermanns. Weak bisimulation for fully probabilistic processes. In Proc. of CAV, pages 119-130, London, UK, 1997. Springer. Google Scholar
  5. H. Beohar and P.J.L. Cuijpers. Open maps in concrete categories and branching bisimulation for prefix orders. ENTCS, 319:51 - 66, 2015. URL: http://dx.doi.org/10.1016/j.entcs.2015.12.005.
  6. H. Beohar and S. Küpper. On path-based coalgebras and weak notions of bisimulation. ArXiv e-prints, May 2017. URL: https://arxiv.org/abs/1705.08715.
  7. F. Bonchi, S. Milius, A. Silva, and F. Zanasi. Killing epsilons with a dagger: A coalgebraic study of systems with algebraic label structure. TCS, 604:102 - 126, 2015. Coalgebraic Methods in Computer Science. Google Scholar
  8. T. Brengos. On Coalgebras with Internal Moves, pages 75-97. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44124-4_5.
  9. T. Brengos. Weak bisimulation for coalgebras over order enriched monads. Logical Methods in Computer Science, 11(2), 2015. URL: http://dx.doi.org/10.2168/LMCS-11(2:14)2015.
  10. T. Brengos, M. Miculan, and M. Peressotti. Behavioural equivalences for coalgebras with unobservable moves. JLAP, 84(6):826 - 852, 2015. URL: http://dx.doi.org/10.1016/j.jlamp.2015.09.002.
  11. P.J.L. Cuijpers. Prefix orders as a general model of dynamics. In I. Mackie, M. Ayala-Rincón, and E. Bonelli, editors, Proc. of Developments in Computation Models, DCM'13, pages 25-29, Buenos Aires, Argentina, 2013. Google Scholar
  12. S. Goncharov and D. Pattinson. Coalgebraic Weak Bisimulation from Recursive Equations over Monads, pages 196-207. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_17.
  13. B. Jacobs and A. Sokolova. Traces, Executions and Schedulers, Coalgebraically, pages 206-220. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03741-2_15.
  14. A. Joyal, M. Nielson, and G. Winskel. Bisimulation and open maps. In Proc. of 8th Annual IEEE Symposium on Logic in Computer Science, pages 418-427, 1993. URL: http://dx.doi.org/10.1109/LICS.1993.287566.
  15. H. Kerstan and B. König. Coalgebraic trace semantics for continuous probabilistic transition systems. Logical Methods in Computer Science, 9(4), 2013. URL: http://dx.doi.org/10.2168/LMCS-9(4:16)2013.
  16. R. Milner. A Calculus of Communicating Systems, volume 92 of Lecture Notes in Computer Science. Springer, Berlin Heidelberg, 1980. Google Scholar
  17. P. Panangaden. Labelled Markov Processes. Imperial College Press, London, 2009. Google Scholar
  18. H. L. Royden and P. M. Fitzpatrick. Real analysis. Pearson, 4superscriptth edition edition, 2010. Google Scholar
  19. J.J.M.M. Rutten. Universal coalgebra: a theory of systems. TCS, 249(1):3 - 80, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(00)00056-6.
  20. A. Sokolova. Personal communication. 11 2016. Google Scholar
  21. A. Sokolova, E. de Vink, and H. Woracek. Weak bisimulation for action-type coalgebras. ENTCS, 122:211 - 228, 2005. URL: http://dx.doi.org/10.1016/j.entcs.2004.06.050.
  22. A. Sokolova, E. de Vink, and H. Woracek. Coalgebraic weak bisimulation for action-type systems. SACS, 19:93-144, 2009. Google Scholar
  23. R.J. van Glabbeek. The linear time - Branching time spectrum II, pages 66-81. Springer, 1993. URL: http://dx.doi.org/10.1007/3-540-57208-2_6.
  24. R.J. van Glabbeek. What is Branching Time Semantics and Why to Use It?, pages 469-479. World Scientific Publishing, River Edge, USA, 2001. Google Scholar
  25. R.J. van Glabbeek and W.P. Weijland. Branching time and abstraction in bisimulation semantics. J. ACM, 43(3):555-600, May 1996. URL: http://dx.doi.org/10.1145/233551.233556.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact