×

\(\tau\)-bisimulations and full abstraction for refinement of actions. (English) Zbl 0743.68060

Summary: We investigate this question and show that branching bisimulation is fully abstract with respect to \(\eta\)-bisimulation, while the fully abstract congruence with respect to \(\tau\)-bisimulation is \(\Delta\)- bisimulation.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q55 Semantics in the theory of computing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aceto, L.; Hennessy, M., Towards action-refinement in process algebra, Proc. 4th IEEE Symp. Logic in Computer Science, Asilomar, CA, 138-145 (1989) · Zbl 0716.68034
[2] Aceto, L.; Hennessy, M., Adding action refinement to a finite process algebra, (Proc. 18th ICALP, Madrid, 510 (1991), Springer: Springer Berlin), 506-519, Lecture Notes in Computer Science · Zbl 0786.68055
[3] Baeten, J. C.M.; van Glabbeek, R. J., Another look at abstraction in process algebra (extended abstract), (Proc. 14th ICALP, Karlsruhe, 267 (1987), Springer: Springer Berlin), 84-94, Lecture Notes in Computer Science · Zbl 0623.68023
[4] Bergstra, J. A.; Klop, J. W., Algebra of communicating processes with abstraction, Theoret. Comput. Sci., 37, 77-121 (1985) · Zbl 0579.68016
[5] De Nicola, R.; Montanari, U.; Vaandrager, F., Back and forth bisimulations, (Proc. CONCUR’90, Amsterdam, 458 (1990), Springer: Springer Berlin), 152-165, Lecture Notes in Computer Science
[6] Devillers, R., Maximality preserving bisimulation, (Tech. Rept. LIT-214, Lab. Informatique Théorique (March 1990), Université Libre de Bruxelles) · Zbl 0780.68036
[7] van Glabbeek, R. J., The refinement theorem for ST-bisimulation semantics, Proc. IFIP Working Conf. on Programming Concepts and Methods, Sea of Galilee, Israel (1990)
[8] van Glabbeek, R. J.; Goltz, U., Equivalence notions for concurrent systems and refinement of actions, (Proc. Math. Found. Computer Science, Porabka-Kozubnik, 379 (1989), Springer: Springer Berlin), 237-248, Lecture Notes in Computer Science · Zbl 0755.68095
[9] van Glabbeek, R. J.; Weijland, W. P., Branching time and abstraction in bisimulation semantics (extended abstract), Research Rept. CS-R8911 (1989), CWI
[10] van Glabbeek, R. J.; Weijland, W. P., Refinement in branching time semantics, Proc. AMAST Conf., Iowa City, 197-201 (1989), Available as CWI Rept. CS-R8922
[11] Hennessy, M., Axiomatising finite concurrent processes, SIAM J. Comput., 17, 5, 997-1017 (1988) · Zbl 0666.68024
[12] Milner, R., (A Calculus of Communicating Systems, 92 (1980), Springer: Springer Berlin), Lecture Notes in Computer Science · Zbl 0452.68027
[13] Vogler, W., Failures semantics of Petri nets and the refinement of places and transitions, (Tech. Rept. TUM-I9003 (January 1990), Institut für Informatik, TUM: Institut für Informatik, TUM Munich)
[14] Vogler, W., Bisimulation and action refinement, (Proc. STACS 91, Hamburg, 480 (1991), Springer: Springer Berlin), 309-321, Lecture Notes in Computer Science · Zbl 0773.68052
[15] Walker, D. J., Bisimulations and divergence, Edinburgh. Edinburgh, Proc. 3rd IEEE Symp. Logic in Computer Science (1988)
[16] Weijland, W. P., Synchrony and asynchrony in process algebra, (Ph.D. Thesis (1989), Univ. Amsterdam) · Zbl 0683.68024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.