Abstract
We suggest an equivalence notion for event structures as a semantic model of concurrent systems. It combines the notion of testing (or failure) equivalence with respect to the timing of choices between different executions with a precise account of causalities between action occurrences as in causal semantics. This fills an open gap in the lattice of equivalences considered in comparative concurrency semantics. We show that our notion coincides with a “canonical” equivalence obtained as the usual testing performed on causal trees. Furthermore, we show that it is invariant under action refinement, thus fulfilling a standard criterion for non-interleaving equivalences.
The research reported in this paper was partially supported by the Human Capital and Mobility Cooperation Network “EXPRESS” (Expressiveness of Languages for Concurrency).
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
Luca Aceto. History preserving, causal and mixed-ordering equivalences over stable event structures. Fundamenta Informaticae, 17, 1992.
Luca Aceto, Rocco De Nicola, and A. Fantechi. Testing equivalences for event structures. In M. Venturini Zilli, editor, Mathematical Models for the Semantics of Parallelism, volume 280 of Lecture Notes in Computer Science, pages 1–20. Springer-Verlag, 1987.
Luca Aceto and Uffe Engberg. Failures semantics for a simple process language with refinement. In S. Biswas and K. V. Nori, editors, Foundations of Software Technology and Theoretical Computer Science, volume 590 of Lecture Notes in Computer Science, pages 89–108. Springer-Verlag, 1991.
Gérard Boudol and Ilaria Castellani. Permutations of transitions: An event structure semantics for CCS and SCCS. In de Bakker et al. [8], pages 411–427.
W. R. Cleaveland, editor. Concur '92, volume 630 of Lecture Notes in Computer Science. Springer-Verlag, 1992.
Philippe Darondeau and Pierpaolo Degano. Causal trees. In G. Ausiello, M. Dezani-Ciancaglini, and S. Ronchi Della Rocca, editors, Automata, Languages and Programming, volume 372 of Lecture Notes in Computer Science, pages 234–248. Springer-Verlag, 1989.
Philippe Darondeau and Pierpaolo Degano. Causal trees=interleaving + causality. In I. Guessarian, editor, Semantics of Systems of Concurrent Processes, volume 469 of Lecture Notes in Computer Science, pages 239–255. Springer-Verlag, 1990.
J. W. de Bakker, W.-P. de Roever, and Grzegorz Rozenberg, editors. Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, volume 354 of Lecture Notes in Computer Science. Springer-Verlag, 1989.
Rocco De Nicola and Matthew Hennessy. Testing equivalences for processes. Theoretical Computer Science, 34:83–133, 1984.
Ursula Goltz and Heike Wehrheim. Causal Testing. Technical Report 5/96, Institut für Informatik, Universität Hildesheim, 1996.
M. Hennessy. Concurrent testing of processes. In Cleaveland [5], pages 94–107.
Lalita Jategaonkar and Albert Meyer. Testing equivalences for Petri nets with action refinement. In Cleaveland [5], pages 17–31.
Robin Milner. Communication and Concurrency. Prentice-Hall, 1989.
Gordon Plotkin and Vaughan Pratt. Teams can see pomsets. extended abstract; available by ftp, August 1990.
Vaughan R. Pratt. Modeling concurrency with partial orders. International Journal of Parallel Programming, 15(1):33–71, 1986.
Frits Vaandrager. An explicit representation of equivalence classes of history preserving bisimulation. Unpublished manuscript, 1989.
R. J. van Glabbeek. The linear time — branching time spectrum. In J. C. M. Baeten and J. W. Klop, editors, Concur '90, volume 458 of Lecture Notes in Computer Science, pages 278–297. Springer-Verlag, 1990.
Rob van Glabbeek. Comparative Concurrency Semantics and Refinement of Actions. PhD thesis, Free University of Amsterdam, 1990.
Rob van Glabbeek and Ursula Goltz. Equivalences and refinement. In I. Guessarian, editor, 18éme. Ecole de Printemps d'Informatique Théorique Semantique du Parallelisme, volume 469 of Lecture Notes in Computer Science, 1990.
Rob van Glabbeek and Ursula Goltz. Refinement of actions in causality based models. In J. W. de Bakker, W.-P. de Roever, and Grzegorz Rozenberg, editors, Stepwise Refinement of Distributed Systems — Models, Formalisms, Correctness, volume 430 of Lecture Notes in Computer Science, pages 267–300. Springer-Verlag, 1990. Report version: Arbeitspapiere der GMD 428, Gesellschaft für Mathematik und Datenverarbeitung.
Walter Vogler. Failure semantics based on interval semiwords is a congruence for refinement. Distributed Computing, (4):139–162, 1991.
Glynn Winskel. An introduction to event structures. In de Bakker et al. [8], pages 364–397.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goltz, U., Wehrheim, H. (1996). Causal testing. In: Penczek, W., Szałas, A. (eds) Mathematical Foundations of Computer Science 1996. MFCS 1996. Lecture Notes in Computer Science, vol 1113. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61550-4_165
Download citation
DOI: https://doi.org/10.1007/3-540-61550-4_165
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61550-7
Online ISBN: 978-3-540-70597-0
eBook Packages: Springer Book Archive