Abstract
We show that observational equivalences for standard, partial and regular algebras are bisimulation equivalences in the setting of open maps, proposed in [JNW93] as an abstract approach to behavioural equivalences of processes. The main advantage of the results is capturing models for sequential and concurrent systems in a uniform framework. In such an abstract setting we formulate the property of determinism, shared by all the algebras considered in this paper, and identify some interesting facts about bisimilarity in the deterministic case. All the results for standard, regular and partial algebras are obtained by the applications of general theorems proved in the paper, which we expect to be applicable also in other contexts.
This work was partially supported by KBN 8 T11C 018 11 grant.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abramsky, C.-H. Luke Ong. Full Abstraction in the Lazy Lambda Calculus. Information and Computation 105(2), 159–267, 1993.
Bidoit, M., Hennicker, R., Wirsing, M. Behavioural and abstractor specifications. Science of Computer Programming 25 (2–3), 1995.
Bidoit, M., Tarlecki, A. Regular algebras: a framework for observational specifications with recursive definitions. Report LIENS-95-12, Ecole Normale Superieure, 1995.
Bidoit, M., Tarlecki A. Behavioural satisfaction and equivalence in concrete model categories. Manuscript. The short version appeared in Proc. 20th Coll. on Trees in Algebra and Computing CAAP'96, Linköping, Springer-Verlag.
Birkhoff, G., Lipson, J.D. Heterogeneous algebras. J. Combinatorial Theory 8 (1970),115–133.
Broy, M., Wirsing, M. Partial abstract data types. Acta Informatica 18 (1982), 47–64.
Cheng, A., Nielsen, M. Open maps (at) work. Research series RS-95-23, BRICS, Department of Computer Science, University of Aarhus, 1995.
Diers, Y., Families universelles de morphismes. Annales de la Societe Scientifique de Bruxelles, 93, nr 3, 1979, 175–195.
Giarratana, V., Gimona, F., Montanari, U. Observability concepts in abstract data type specification. Proc. 5th Intl. Symp. Mathematical Foundations of Computer Science, Gdańsk 1976, LNCS 45, Springer-Verlag 1976, 576–587.
Goguen, J.A., Thatcher, J.W., Wagner, E.G. An initial algebra approach to the specification, correctness and implementation of abstract data types. Current Trends in Programming Methodology 4, Data Structuring, Yeh, R.T., ed., 80–149, Prentice-Hall 1978.
Gordon, A. A tutorial on co-induction and functional programming. Proc. of the 1994 Glasgow Workshop on Functional Programming, Springer Workshops in Computing, 1995, 78–95.
Jacobs, B.F.P. Objects and classes, coalgebraically. Technical Report CSR9536, CWI, 1995.
Joyal, A., Moerdijk, I. A completeness theorem for open maps. Annals of Pure and Applied Logic 70 (1994), 51–86.
Joyal, A., Nielsen, G. Winskel, Bisimulation and open maps. Proc. 8th Annual Symposium on Logic in Computer Science LICS'93, 1993, 418–427.
Lasota, S. Open Maps as a Bridge between Algebraic Observational Equivalence and Bisimilarity. Technical report 97-12 (249), Institute of Informatics, Warsaw University. Accesible at http://zls.mimuw.edu.pl/~sl.
Lasota, S. Partial Congruence Factorization of Bisimilarity Induced by Open Maps. Manuscript, accesible at http://zls.mimuw.edu.pl/~sl.
Malcolm, G. Behavioural equivalence, bisimilarity, and minimal realisation. Recent Trends in Data Type Specification, 11th Workshop on Specification of Abstract Data Types, Oslo, 1995. LNCS 1130, 359–378.
Milner, R. Communication and concurrency. Prentice-Hall International Series in Computer Science, C. A. R. Hoare series editor, 1989.
Morris, J. H. Lambda-Calculus Models of Programming Languages. Ph.D. thesis, MIT, 1968.
Park, D.M.R. Concurrency and Automata on Infinite Sequences. Proc. 5th G.I. Conference, Lecture Notes in Computer Science 104, Springer-Verlag, 1981.
Reichel, H. Behavioural equivalence-a unifying concept for initial and final specification methods. Proc. 3rd Hungarian Computer Science Conference, Mathematical Models in Computer Systems, M. Arato, L. Varga, eds., Budapest, 27–39, 1981.
Sannella, D., Tarlecki, A. On observational equivalence and algebraic specification. J. Computer and System Sciences 34 (1987), 150–178.
Tarlecki, A., Wirsing, M. Continuous abstract data types. Fundamenta Informaticae 9 (1986), 95–126.
Tiuryn, J. Fixed-points and algebras with infinitely long expressions. Part l. Regular algebras. Fundamenta Informaticae 2 (1978), 102–128.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lasota, S. (1998). Open maps as a bridge between algebraic observational equivalence and bisimilarity. In: Presicce, F.P. (eds) Recent Trends in Algebraic Development Techniques. WADT 1997. Lecture Notes in Computer Science, vol 1376. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-64299-4_40
Download citation
DOI: https://doi.org/10.1007/3-540-64299-4_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64299-2
Online ISBN: 978-3-540-69719-0
eBook Packages: Springer Book Archive