On the semantics of concurrency: Partial orders and transition systems
Lecture notes in computer sciencePublished 1 January 1987
Gérard Boudol, Ilaria Castellani
Citations94
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algebra of labelled event structures whose operations are sequential composition, sum, and parallel composition is introduced and it is claimed that the bisimulation relative to such transition systems brings out a clean distinction between concurrency and sequential non-determinism.
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.
Keywords
Computer Science
Lecture notes in computer scienceConcurrency and automata on infinite sequences
1,861 Citations2005David Park
A general method for proving/deciding equivalences between omega-regular languages, whose recognizers are modified forms of Buchi or Muller-McNaughton automata, derived from Milner's notion of “simulation” is obtained.
Journal of the ACMAlgebraic laws for nondeterminism and concurrency
1,361 Citations1985Matthew Hennessy, Robin Milner
The paper demonstrates, for a sequence of simple languages expressing finite behaviors, that in each case observation congruence can be axiomatized algebraically and the algebraic language described here becomes a calculus for writing and specifying concurrent programs and for proving their properties.
Petri Nets
1,322 Citations1985Wolfgang Reisig
The author presents an example for Applying S-Invariants: The Verification of Facts in C/E-Systems by Means of S- Invariants, a model based on the successful implementation of Nets Analysis in the context of Logic Circuits and Operating Systems.
Theoretical Computer SciencePetri nets, event structures and domains, part I
915 Citations1981Mogens Nielsen, Gordon Plotkin +1 more
To connect the abstract ideas of events and domains of information, it is shown how casual nets induce certain kinds of domains where the information points are certain sets of events, which allows translations between the languages of net theory and domain theory.
Theoretical Computer ScienceCalculi for synchrony and asynchrony
898 Citations1983Robin Milner
It is shown that the author's Calculus of Communicating Systems (1980), which is an asynchronous model, is derivable from the calculus presented here, which models both synchronous and asynchronous computation.
DAIMI Report SeriesConcurrent Program Schemes and their Interpretations
570 Citations1977Antoni Mazurkiewicz
It is shown that to each scheme corresponds a set of equations determining the result of the scheme; it is shown how these equations can be solved and that the solutions of these equations are regular trace languages.
Information and ControlThe non-sequential behaviour of Petri nets
295 Citations1983Ursula Goltz, Wolfgang Reisig
Some theorems relating K -density, cut finiteness, and discreteness are proved and the result that a place/transition net is bounded if and only if its processes are K -dense is obtained.
Lecture notes in computer scienceEvent structure semantics for CCS and related languages
237 Citations1982Glynn Winskel
This work gives denotational semantics to a wide range of parallel programming languages based on the idea of Milner’s CCS, that processes communicate by events of mutual synchronization, and gets an event structure semantics for CCS.
On the composition of processes
103 Citations1982Vaughan Pratt
A model of net-connected processes is described that amounts to a reformulation of a model derived by Brock and Ackerman from the Kahn-McQueen model of processes as relations on streams of data, which leads directly to a straightforward definition of process composition.
Notes on Algebraic Calculi of Processes
88 Citations1985Gérard Boudol
The intoduce a calculus called MEIJE built on a monoid of synchronized actions and illustrate some general semantic notions and the concept of subcalculus is illustrated through the description in the language of the class of rational parallel place machines.
Lecture notes in computer scienceBehavioural equivalence relations induced by programming logics
76 Citations2006Stephen Brookes, William C. Rounds
This paper compares the descriptive power of three programming logics by studying the elementary equivalence relations which the logics induce on nondeterministic state-transition systems and finds that the notions of bisimilarity, Ogden, and observation equivalence are very strong equivalences compared with those induced by theLogics.
Lecture notes in computer scienceLectures on a calculus for communicating systems
59 Citations1985Robin Milner
Theoretical Computer ScienceBehaviours of concurrent systems
57 Citations1980Józef Winkowski
The behaviour of a system is defined as a set of processes which can be obtained by composing certain elementary processes, and which sets of processes are the behaviours of concurrent systems are explained.
Physiological MeasurementPartial orders and the axiomatic theory of shuffle (pomsets)
48 Citations1985Jay Loren Gischer
It is shown, among other results, that the theory of sets of pomsets under addition, shuffle, and concatenation is finitely axiomatizable, and that languages of strings of length two are sufficient to distinguish pomset which are not language-equivalent.
Labeled Event Structures: A Model for Observable Concurrency.
28 Citations1982Ilaria Castellani, Paola Franceschi +1 more
Despite having increased BMD compared with controls, subjects with OA did not have a significantly reduced risk of osteoporotic fracture, although there was a trend toward a reduction of femoral neck fractures in subjects with severe radiographic OA.
Lecture notes in computer sciencePartial ordering derivations for CCS
27 Citations1985Pierpaolo Degano, Rocco De Nicola +1 more
This paper extends CCS transitions, labelled by strings, to concurrent histories, i.e. to transitions labelled by partial orderings, by a theorem which shows that the strings can be obtained by taking all interleavings compatible with the partial ordering.
Lecture notes in computer scienceK-density, N-density, and finiteness properties
14 Citations1985Helmut Plünnecke
It turns out that much weaker properties are sufficient; especially, it will be proved that an N-dense non-empty poset is K-dens if all cuts are finite.
Distributed Systems, Partial Orderings of Events, and Event Structures
9 Citations1986Pierpaolo Degano, Ugo Montanari
These lecture notes are divided in two parts, dedicated to two models, concurrent histories and Graphs for Distributed Systems (GDS), both based on partial orderings, both of which are largely consistent.