Abstract
We introduce an algebra of labelled event structures whose operations are sequential composition, sum, and parallel composition. A transition relation is defined on these objects, where at each step a process performs a labelled poset. It is claimed that the bisimulation relative to such transition systems brings out a clean distinction between concurrency and sequential non-determinism.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
G. Boudol, Notes on Algebraic Calculi of Processes, in Logics and Models of Concurrent Systems (K. Apt, Ed.) NATO ASI Series F13, Springer-Verlag (1985) 261–303.
G. Boudol, I. Castellani, Concurrency and Communication, full version of this paper, in preparation (1986).
S. Brookes, W. C. Rounds, Behavioural Equivalence Relations Induced by Programming Logics, ICALP 83, Lecture Notes in Comput. Sci. 154 (1983) 97–108.
I. Castellani, P. Franceschi, U. Montanari, Labelled Event Structures: a Model for Observable Concurrency, in Formal Description of Programming Concepts 2 (D. Bjørner, Ed.), North-Holland (1983) 383–400.
I. Castellani, M. Hennessy, Distributed Bisimulations, to be published (1985).
Ph. Darondeau, L. Kott, On the Observational Semantics of Fair Parallelism, ICALP 83, Lecture Notes in Comput. Sci. 154 (1983) 147–159.
P. Degano, U. Montanari, Distributed Systems, Partial Ordering of Events and Event Structures, in Control Flow and Data Flow: Concepts of Distributed Programming (M. Broy, Ed.), NATO ASI Series F14, Springer-Verlag (1985) 7–106.
P. Degano, R. de Nicola U. Montanari, Partial Ordering Derivations for CCS, FCT 85, Lecture Notes in Comput. Sci. 199 (1985) 520–533.
H. J. Genrich, E. Stankiewicz-Wiechno, A Dictionary of Some Basic Notions of Net Theory, in Net Theory and Applications (W. Brauer, Ed.) Lecture Notes in Comput. Sci. 84 (1980) 519–531.
J. L. Gischer, Partial Orders and the Axiomatic Theory of Shuffle, Ph. D. Thesis Stanford University (1984).
U. Goltz, W. Reisig, The Non-sequential Behaviour of Petri Nets, Information and Control 57 (1983) 125–147.
J. Grabowski, On Partial Languages, Fundamentae Informaticae IV.2 (1981) 427–498.
P. A. Grillet, Maximal Chains and Antichains, Fund. Math. 65 (1969) 157–167.
M. Hennessy, R. Milner, Algebraic Laws for Nondeterminism and Concurrency, JACM 32 (1985) 137–161.
A. Mazurkiewicz, Concurrent Program Schemes and their Interpretations, Aarhus Workshop on Verification of Parallel Programs, Daimi PB-78, Aarhus University (1977).
A. Mazurkiewicz, Traces, Histories, Graphs: Instances of a Process Monoid, MFCS 84, Lecture Notes in Comput. Sci. 176 (1984) 115–133.
R. Milner, A Calculus of Communicating Systems, Lecture Notes in Comput. Sci. 92 (1980).
R. Milner, Calculi for Synchrony and Asynchrony, Theoret. Comput. Sci. 25 (1983) 267–310.
R. Milner, Lectures on a Calculus for Communicating Systems, Seminar on Concurrency, Lecture Notes in Comput. Sci. 197 (1985) 197–220.
M. Nielsen, G. Plotkin, G. Winskel, Petri Nets, Event Structures and Domains, Theoret. Comput. Sci. 13 (1981) 85–108.
D. Park, Concurrency and Automata on Infinite Sequences, 5th GI Conf., Lecture Notes in Comput. Sci. 104 (1981) 167–183.
C. A. Petri, Non-sequential Processes, GMD-ISF Rep. 77-05 (1977).
G. Plotkin, A Structural Approach to Operational Semantics, Daimi FN-19, Aarhus University (1981).
G. Plotkin, An Operational Semantics for CSP, in Formal Description of Programming Concepts 2 (D. Bjørner, Ed.), North-Holland (1983) 199–225.
H. Plünnecke, K-Density, N-Density and Finiteness Properties, in Advances in Petri Nets 84 (G. Rozenberg, Ed.) Lecture Notes in Comput. Sci. 188 (1984) 392–412.
V. R. Pratt, On the Composition of Processes, 9th POPL (1982) 213–223.
V.R. Pratt, The Pomset Model of Parallel Processes: Unifying the Temporal and the Spatial, Seminar on Concurrency, Lecture Notes in Comput. Sci. 197 (1985) 180–196.
W. Reisig, On the Semantics of Petri Nets, in Formal Models in Programming (G. Chroust, E.J. Neuhold, Eds.), North-Holland (1985) 347–372.
M. W. Shields, Concurrent Machines, The Computer Journal 28 (1985) 449–465.
J. Winkowski, Algebras of Partial Sequences, FCT 77, Lecture Notes in Comput. Sci. 56 (1977) 187–196.
J. Winkowski, Behaviours of Concurrent Systems, Theoret. Comput. Sci. 12 (1980) 39–60.
G. Winskel, Events in Computation, Ph. D. Thesis, Edinburgh University (1980).
G. Winskel, Event Structure Semantics for CCS and Related Languages, Daimi PB-159, Aarhus University (1983).
G. Winskel, Categories of Models for Concurrency, Seminar on Concurrency, Lecture Notes in Comput. Sci. 197 (1985) 246–267.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boudol, G., Castellani, I. (1987). On the semantics of concurrency: Partial orders and transition systems. In: Ehrig, H., Kowalski, R., Levi, G., Montanari, U. (eds) TAPSOFT '87. CAAP 1987. Lecture Notes in Computer Science, vol 249. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-17660-8_52
Download citation
DOI: https://doi.org/10.1007/3-540-17660-8_52
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-17660-2
Online ISBN: 978-3-540-47746-4
eBook Packages: Springer Book Archive