Abstract
Bisimulation-up-to enhances the bisimulation proof method for process equivalence. We present its generalization from labelled transition systems to arbitrary coalgebras, and show that for a large class of systems, enhancements such as bisimulation up to bisimilarity, up to equivalence and up to context are sound proof techniques. This allows for simplified bisimulation proofs for many different types of state-based systems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aczel, P., Mendler, N.: A Final Coalgebra Theorem. In: Dybjer, P., Pitts, A.M., Pitt, D.H., Poigné, A., Rydeheard, D.E. (eds.) Category Theory and Computer Science. LNCS, vol. 389, pp. 357–365. Springer, Heidelberg (1989)
Bartels, F.: On generalised coinduction and probabilistic specification formats. PhD thesis, CWI, Amsterdam (2004)
Bonchi, F., Bonsangue, M., Boreale, M., Rutten, J., Silva, A.: A coalgebraic perspective on linear weighted automata. Inf. Comput. 211, 77–105 (2012)
Bonchi, F., Pous, D.: Checking NFA equivalence with bisimulations up to congruence. In: POPL (to appear, 2013)
Gumm, H.P.: Elements of the general theory of coalgebras. In: LUATCS 1999 Rand Afrikaans University, South Africa (1999)
Klin, B.: Bialgebras for structural operational semantics: An introduction. TCS 412(38), 5043–5069 (2011)
Lenisa, M.: From set-theoretic coinduction to coalgebraic coinduction: some results, some problems. ENTCS 19, 2–22 (1999)
Milner, R.: Calculi for synchrony and asynchrony. TCS 25, 267–310 (1983)
Pous, D., Sangiorgi, D.: Enhancements of the bisimulation proof method. In: Advanced Topics in Bisimulation and Coinduction, pp. 233–289. Cambridge University Press (2012)
Rutten, J.: Automata and Coinduction (An Exercise in Coalgebra). In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 194–218. Springer, Heidelberg (1998)
Rutten, J.: Universal coalgebra: a theory of systems. TCS 249(1), 3–80 (2000)
Rutten, J.: Behavioural differential equations: a coinductive calculus of streams, automata, and power series. TCS 308(1-3), 1–53 (2003)
Sangiorgi, D.: On the bisimulation proof method. Math. Struct. Comp. Sci. 8(5), 447–479 (1998)
Zhou, X., Li, Y., Li, W., Qiao, H., Shu, Z.: Bisimulation Proof Methods in a Path-Based Specification Language for Polynomial Coalgebras. In: Ueda, K. (ed.) APLAS 2010. LNCS, vol. 6461, pp. 239–254. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rot, J., Bonsangue, M., Rutten, J. (2013). Coalgebraic Bisimulation-Up-To. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds) SOFSEM 2013: Theory and Practice of Computer Science. SOFSEM 2013. Lecture Notes in Computer Science, vol 7741. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35843-2_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-35843-2_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35842-5
Online ISBN: 978-3-642-35843-2
eBook Packages: Computer ScienceComputer Science (R0)