Abstract
Event structure models often have some constraint which ensures that for each system run it is clear what are the causal predecessors of an event (i.e. there is no causal ambiguity). In this contribution we study what happens if we remove such constraints. We define five different partial order semantics that are intentional in the sense that they refer to syntactic aspects of the model. We also define an observational partial order semantics, that derives a partial order from just the event traces.
It appears that this corresponds to the so-called early intentional semantics; the other intentional semantics cannot be observationally characterized. We study the equivalences induced by the different partial order definitions, and their interrelations.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Boudol and I. Castellani. Flow models of distributed computations: three equivalent semantics for CCS. Information and Computation, 114:247–314, 1994.
J.W. de Bakker, W.-P. de Roever, and G. 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.
L. Ferreira Pires. Architectural Notes: A Framework for Distributed Systems Development. PhD thesis, University of Twente, 1994.
J-P. Katoen. Quantitative and Qualitative Extensions of Event Structures. CTIT Ph. D-thesis series no. 96-09, University of Twente, 1996.
R. Langerak. Transformations and Semantics for LOTOS. PhD thesis, University of Twente, 1992.
R. Langerak. Bundle event structures: a non-interleaving semantics for LOTOS. In M. Diaz and R. Groz, editors, Formal Description Techniques V, volume C-10 of IFIP Transactions, pages 331–346. North-Holland, 1993.
R. Langerak, E. Brinksma, and J.-P. Katoen. Causal ambiguity and partial orders in event structures. CTIT technical report, University of Twente, 1997.
R. Loogen and U. Goltz. Modelling nondeterministic concurrent processes with event structures. Fundamentae Informaticae, 14:39–74, 1991.
V.R. Pratt. Modeling concurrency with partial orders. International Journal of Parallel Programming, 15(1):33–71, 1986.
A. Rensink. Models and Methods for Action Refinement. PhD thesis, University of Twente, 1993.
Rob van Glabbeek. Comparative Concurrency Semantics and Refinement of Actions. PhD thesis, Free University of Amsterdam, 1990.
G. Winskel. Events in Computation. PhD thesis, University of Edinburgh, 1980. (also available as Technical Report CST-10-80).
G. Winskel. An introduction to event structures. In de Bakker et al. [dBdRR89], pages 364–397.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Langerak, R., Brinksma, E., Katoen, JP. (1997). Causal ambiguity and partial orders in event structures. In: Mazurkiewicz, A., Winkowski, J. (eds) CONCUR '97: Concurrency Theory. CONCUR 1997. Lecture Notes in Computer Science, vol 1243. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63141-0_22
Download citation
DOI: https://doi.org/10.1007/3-540-63141-0_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63141-5
Online ISBN: 978-3-540-69188-4
eBook Packages: Springer Book Archive