Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T13:13:44.116Z Has data issue: false hasContentIssue false
  • English
  • Français

Bisimulation proof methods in a path-based specification language for polynomial coalgebras†

Published online by Cambridge University Press:  10 November 2014

XIAO-CONG ZHOU ,
YONG-JI LI ,
WEN-JUN LI ,
HAI-YAN QIAO  and
ZHONG-MEI SHU
XIAO-CONG ZHOU
Affiliation:
School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510275, P. R. China E-mail: [email protected]
YONG-JI LI
Affiliation:
School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510275, P. R. China E-mail: [email protected]
WEN-JUN LI
Affiliation:
School of Software, Sun Yat-sen University, Guangzhou 510275, P. R. China
HAI-YAN QIAO
Affiliation:
School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510275, P. R. China E-mail: [email protected]
ZHONG-MEI SHU
Affiliation:
School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510275, P. R. China E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

What reasoning rules can be used for the deduction of bisimulation formulas in coalgebraic specifications is problematic because those rules used in algebraic specifications possibly cannot be applied to bisimulation formulas. Although some categorical bisimulation proof methods for coalgebras have been proposed, they are not based on specification languages of coalgebras so that they cannot be used as reasoning rules. In this paper, a specification language based on paths of polynomial functors is proposed to specify polynomial coalgebras. Paths of polynomial functors give detailed observations and transitions on the state space of coalgebras so that the techniques used in transition system specifications can be applied to such a path-based language. In particular, because bisimulations can be characterized by paths, the notions of progressions, respectful functions and faithful contexts can be defined based on paths, and then bisimulation up-to proof techniques, including bisimulation up-to bisimilarities and up-to contexts for transition systems can be transformed into reasoning rules in the language. Several examples illustrate how to reason syntactically about bisimulations in the language by using the rules induced by the bisimulation proof techniques.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 25 , Issue 4: APLAS 2010 , May 2015 , pp. 765 - 804
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Supported by the National Natural Science Foundation of China under Grant No. 60673050 and the Fundamental Research Funds for the Central Universities of China under Grant No. 11LGPY39.

References

Bartels, F. (2003) Generalised coinduction. Mathematical Structures in Computer Science 13 321–348.Google Scholar
Bonsangue, M., Rutten, J. and Silva, A. (2007) Regular expressions for polynomial coalgebras. Technical Report SEN-E0703, Centrum voor Wiskunde en Informatica (CWI).Google Scholar
Bonsangue, M., Rutten, J. and Silva, A. (2009) An algebra for Kripke polynomial coalgebras. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society, Los Angeles, CA, USA49–58.Google Scholar
Capretta, V. (2010) Bisimulations generated from corecursive equations. In: Mislove, M. and Selinger, P. (eds.) Proceedings of the 26th Conference on the Mathematical Foundations of Programming Semantics, Elsevier Electronic Notes in Theoretical Computer Science 265 245–258.Google Scholar
Capretta, V. (2011) Coalgebras in functional programming and type theory. Theoretical Computer Science 412 5006–5024.Google Scholar
Cîrstea, C. (2000) Integrating Observations and Computations in the Specification of State-based, Dynamical Systems, Ph.D. thesis, University of Oxford.Google Scholar
Goldblatt, R. (2001) A calculus of terms for coalgebras of polynomial functors. In: Corradini, A., Lenisa, M. and Montanari, U. (eds.) Proceedings of Coalgebraic Methods in Computer Science. Elsevier Electronic Notes in Theoretical Computer Science 44 (1)161–184.Google Scholar
Goldblatt, R. (2003a) Equational logic of polynomial coalgebras. In: Balbiani, P., Suzuki, N.-Y., Wolter, F. and Zakharyaschev, M. (eds.) Advances in Modal Logic, volume 4, King's College Publications 149–184.Google Scholar
Goldblatt, R. (2003b) Observational ultraproducts of polynomial coalgebras. Annals of Pure and Applied Logic 123 235–290.Google Scholar
Goldblatt, R. (2006) A modal proof theory for final polynomial coalgebras. Theoretical Computer Science 360 1–22.Google Scholar
Hughes, J. and Jacobs, B. (2004) Simulations in coalgebra. Theoretical Computer Science 327 (1–2)71–108.Google Scholar
Jacobs, B. (1998) Coalgebraic reasoning about classes in object-oriented languages. In: Proceedings of Coalgebraic Methods in Computer Science. Elsevier Electronic Notes in Theoretical Computer Science 11 231–242.Google Scholar
Jacobs, B. (1999) The temporal logic of coalgebras via Galois algebras, Technical Report CSI-R9906, Computer Science Institution, University of Nijmegen.Google Scholar
Jacobs, B. (2000) Towards a duality result in coalgebraic modal logic. In: Reichel, H. (ed.) Proceedings of Coalgebraic Methods in Computer Science. Elsevier Electronic Notes in Theoretical Computer Science 33 160–195.Google Scholar
Jacobs, B. (2001) Many-sorted coalgebraic modal logic: a model-theoretical study. Theoretical Informatics and Applications 35 (1)31–59.Google Scholar
Jacobs, B. (2002) Exercises in coalgebraic specification. In: Backhouse, R., Crole, R. and Gibbons, J. (eds.) Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. Springer Lecture Notes in Computer Science 2297 237–280.Google Scholar
Jacobs, B. (2005) Introduction to Coalgebra: Towards Mathematics of States and Observations. Book Draft, Available at http://www.cs.ru.nl/~bart.Google Scholar
Kupke, C. and Pattinson, D. (2011) Coalgebraic semantics of modal logics: An overview. Theoretical Computer Science 412 5070–5094.Google Scholar
Kupke, C. and Venema, Y. (2008). Coalgebraic automata theory: basic results. Logical Methods in Computer Science 4 1–43.Google Scholar
Kurz, A. (2001) Specifying coalgebras with modal logic. Theoretical Computer Science 260 (1–2)119–138.CrossRefGoogle Scholar
Lenisa, M. (1999) From set-theoretic coinduction to coalgebraic coinduction: Some results, some problems. In: Jacobs, B. and Rutten, J. (eds.) Coalgebraic Methods in Computer Science. Electronic Notes in Theoretical Computer Science 19 1–21.Google Scholar
Luo, L. (2006) An effective coalgebraic bisimulation proof method. In: Proceedings of the 8th Workshop on Coalgebraic Methods in Computer Science. Elsevier Electronic Notes in Theoretical Computer Science 164 105–119.Google Scholar
Moss, L. (1999) Coalgebraic logic. Annals of Pure and Applied Logic 96 (1–3)277–317.Google Scholar
Pattinson, D. (2003) Coalgebraic modal logic: Soundness, completeness and decidability of local consequence. Theoretical Computer Science 309 (1–3)177–193.Google Scholar
Rößiger, M. (1999) Languages for coalgebras on datafunctors. In: Jacobs, B. and Rutten, J. (eds.) Proceedings of Coalgebraic Methods in Computer Science. Elsevier Electronic Notes in Theoretical Computer Science 19 39–60.Google Scholar
Rößiger, M. (2001) From modal logic to terminal coalgebras. Theoretical Computer Science 260 209–228.Google Scholar
Rothe, J., Tews, H. and Jacobs, B. (2001) The coalgebraic class specification language CCSL. Journal of Universal Computer Science 7 (2)175–193.Google Scholar
Rutten, J. (2000) Universal coalgebra: A theory of systems. Theoretical Computer Science 249 3–80.Google Scholar
Rutten, J. (2001) Elements of stream calculus (an extensive exercise in coinduction). In: Brooks, S. and Mislove, M. (eds.) Proceedings of Mathematical Foundations of Programming Semantics. Elsevier Electronic Notes in Theoretical Computer Science 45 1–66.Google Scholar
Sangiorgi, D. (1998) On the bisimulation proof method. Mathematical Structures in Computer Science 8 447–479.Google Scholar
Sangiorgi, D. (2009) On the origins of bisimulation and coinduction. ACM Transactions on Programming Languages and Systems 31 (4) Article 15.Google Scholar
Sangiorgi, D. and Walker, D. (2001) The pi-Calculus: A Theory of Mobile Processes. Cambridge University Press.Google Scholar
Zhou, X.-C., Li, Y.-J., Li, W.-J., Qiao, H.-Y. and Shu, Z.-M. (2010) Bisimulation proof methods in a path-based specification language for polynomial coalgebras. In: Ueda, K. (eds.) Proceedings of ASIAN Symposium on Program Languages and Systems, APLAS'10. Springer Lecture Notes in Computer Science 6461 239–254.Google Scholar