Abstracts
The following is a list of abstracts of and references to my papers,
followed by addresses where they can be ordered.
Here is a list of just the papers.
Here are the
references in
bibtex format.
And here are pointers to my papers sorted by subject.
In the cohomology theory of differentiable manifolds, e.g.
in the proof of the De Rhamtheorem and the treatment of
Poincaréduality, it is used that every open covering
of a paracompact differentiable manifold has a refinement
with the property that every nonempty intersection of a
finite collection of its open sets is diffeomorphic with an
open ball. A covering with this property is called "good".
The existence of such good refinements is usually proved by
referring to some theorems in differential geometry, which
are out of the scope of cohomology theory. The aim of this
paper is to show how to obtain good coverings in an
elementary way, without using differential geometry.
Keywords: Cohomology, differentiable manifolds, open coverings,
convexity, diffeomorphism.
In this paper the methodology of some theories of
concurrency (mainly CCS and CSP) is analysed, focusing on
the following topics: the representation of processes, the
identification issue, and the treatment of nondeterminism,
communication, recursion, abstraction, divergence and
deadlock behaviour. Process algebra turns out to be a
useful instrument for comparing the various theories.
Keywords: Concurrency, process algebra, CCS, CSP, semantic equivalences
This paper presents a new semantics of ACP_tau, the Algebra
of Communicating Processes with abstraction. This leads to
a term model of ACP_tau which is isomorphic [see
erratum] to the model of
process graphs modulo rooted taudeltabisimulation of
Baeten, Bergstra & Klop [TCS 51], but in which no special
rootedness condition is needed. Bisimilarity turns out to
be a congruence in a natural way.
In this model, the Recursive Definition Principle (RDP),
the Commutativity of Abstraction (CA) and Koomen's Fair
Abstraction Rule (KFAR) are satisfied, but the
Approximation Induction Principle (AIP) is not. The
combination of these four principles is proven to be
inconsistent, while any combination of three of them is
not.
In [TCS 51] a restricted version of AIP is proved valid in
the graph model. This paper proposes a simpler and less
restrictive version of AIP, not containing guarded
recursive specifications as a parameter, which is still
valid. This infinitary rule is formulated with the help of
a family B_n of unary predicates, expressing bounded
nondeterminism.
Keywords: Concurrency, process algebra, ACP, Approximation Induction
Principle, Recursion, Abstraction, Fairness, Liveness,
Consistency, Bisimulation, Bounded Nondeterminism
Central to theories of concurrency is the notion of
abstraction. Abstraction from internal actions is the most
important tool for system verification.
In this paper, we look at abstraction in the framework of
the Algebra of Communicating Processes (ACP) of Bergstra &
Klop. We introduce a hidden step eta, and construct a model
for the resulting theory ACP_eta. We briefly look at
recursive specifications, fairness and protocol
verification in this theory, and discuss the relations with
Milner's silent step tau.
Keywords: Concurrency, process algebra, ACP, abstraction, bisimulation
 CWI report CSR8701. Available as
Scanned
PDFfile.
 Extended abstract in:
Automata, Languages and Programming,
Proceedings 14th International Colloquium, ICALP 87,
Karlsruhe, Germany, July 1987 (Th. Ottman, ed.), LNCS 267,
SpringerVerlag, 1987, pp. 8494. Available as
Scanned
PDFfile.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#3
In Vrancken, the empty process was added to the Algebra of
Communicating Processes of Bergstra & Klop. Reconsidering
the definition of the parallel composition operator merge,
we found that it is preferable to explicitly state the
termination option. This gives an extra summand in the
defining equation of merge, using the auxiliary operator
tick. We find that tick can be defined in terms of the
encapsulation operator. We give an operational and a
denotational semantics for the resulting system ACPtick,
and prove that they are equal. We consider the Limit Rule,
and prove it holds in our models.
Keywords: Concurrency, process algebra, ACP, empty process, termination,
tick, bisimulation
 CWI report CSR8716. Available as
Scanned
PDFfile.
 In: Proceedings Seventh Conference on Foundations of Software
Technology and Theoretical Computer Science, Pune, India,
December 1987 (K.V. Nori, ed.), LNCS 287, SpringerVerlag,
1987, pp. 153172. Available as
Scanned
PDFfile.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#4
In this paper, we combine the hidden step eta of
3 with the empty process of Vrancken and 4. We formulate a system ACPc, which is a
conservative extension of the systems ACP_eta and
ACPtick, but also of ACP_tau. Abstraction
from internal steps can be achieved in two ways, in two
stages: we can abstract to the hidden step eta, and
then from eta to Milner's silent step tau.
Keywords: Concurrency, process algebra, ACP, abstraction, empty process,
termination, bisimulation
 CWI report CSR8721. Available as
Scanned
PDFfile.
 Fundamenta Informaticae XII, 1989, pp. 221242.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#5
In this paper we discuss the issue of interleaving
semantics versus True concurrency in an algebraic setting.
We present various equivalence notions on Petri nets which
can be used in the construction of algebraic models:
 the occurrence net equivalence of Nielsen, Plotkin and Winskel;
 bisimulation equivalence, which leads to a model which
is isomorphic to the graph model of Baeten, Bergstra & Klop;
 the concurrent bisimulation equivalence, which is also
described by Nielsen & Thiagarajan, and Goltz;
 partial order equivalences which are inspired by work
of Pratt, and Boudol & Castellani.
A central role in the paper will be played by the notion of
realtime consistency. We show that, besides occurrence net
equivalence, none of the equivalences mentioned above
(including the partial order equivalences!) is realtime
consistent. Therefore we introduce the notion of
STbisimulation equivalence, which is realtime consistent.
Moreover a complete proof system will be presented for
those finite STbisimulation processes in which no action
can occur concurrently with itself.
Keywords: Concurrency, process algebra, ACP, Petri nets, semantic
equivalences, interleaving vs. partial orders,
bisimulation, realtime consistency.
Keywords: Concurrency, Labelled transition systems, Nondeterminism,
Abstraction, Semantic equivalences, Linear time, Branching time,
Trace semantics, Failure semantics, Failure trace semantics,
Readiness semantics, Ready trace semantics, Stable bisimulation,
Weak bisimulation, BCCS, BCSP, Complete axiomatisations.
 Syllabus processemantieken, deel 2. Handwritten manuscript, in Dutch.
In recent years a wide variety of process algebras has
been proposed in the literature. Often these process
algebras are closely related: they can be viewed as
homomorphic images, submodels or restrictions of each
other. The aim of this paper is to show how the semantical
reality, consisting of a large number of closely related
process algebras, can be reflected, and even used, on the
level of algebraic specifications and in process
verifications. This is done by means of the notion of a
module. The simplest modules are building blocks of
operators and axioms, each block describing a feature of
concurrency in a certain semantical setting. These modules
can then be combined by means of a union operator +, an
export operator [], allowing to forget some operators in a
module, an operator H, changing semantics by taking
homomorphic images, and an operator S which takes
subalgebras. These operators enable us to combine modules
in a subtle way, when the direct combination would be
inconsistent. We show how auxiliary process algebra
operators can be hidden when this is needed. Moreover it is
demonstrated how new process combinators can be defined in
terms of more elementary ones in a clean way. As an
illustration of our approach, a methodology is presented
that can be used to specify FIFOqueues, and that
facilitates verification of concurrent systems containing
these queues.
Keywords: Concurrency, process algebra, ACP, modular algebraic
specifications, export operator, union of modules,
homomorphism operator, subalgebra operator, FIFOqueues,
chaining operator, communication protocols.
Note: Most of this material is also included in 22.
 CWI report CSR8821
 Appeared as Chapter II of my Ph.D. Thesis.
 Extended abstract in: Algebraic Methods: Theory, Tools and
Applications (M. Wirsing & J.A. Bergstra, eds.), LNCS 394,
SpringerVerlag, 1989, pp. 465506.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#7
Keywords: Concurrency, compositionality, CCSP, Petri nets, event
structures, pomsets, semantic equivalences, interleaving
vs. partial orders, temporal logic, action refinement.
 Arbeitspapiere der GMD 320, Sankt Augustin, Germany 1988.
An operational noninterleaved process graph semantics of CCSP
R.J. van Glabbeek (CWI)
March 1988
In this talk I argue that, contrary to what is widely
believed, process graphs, or labelled transition systems,
have enough structure to model noninterleaved features of
concurrency. Moreover a noninterleaved process graph
semantics of the system description language CCSP (a
combination of CCS and CSP) is provided, using Plotkin's
structural operational approach. Furthermore, criteria for
semantic equivalences for concurrent systems are proposed
and evaluated.
Keywords: Concurrency, CCSP, process graphs, event structures,
Petri nets, structural operational semantics, semantic equivalences.
 In 8, pp. 1819.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#graph
In a natural formulation, Craig's interpolation theorem is
shown to hold for equational logic. We also discuss the
prevalent claims that equational logic does not have the
interpolation property.
Keywords: Interpolation, Craig's lemma, equational logic, similarity,
module algebra, splitting interpolation.
 CWI report CSR8838

 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#9
We investigate equivalence notions for concurrent systems.
We consider "linear time" approaches where the system
behaviour is characterized as the set of possible runs as
well as "branching time" approaches where the conflict
structure of systems is taken into account. We show that
the usual interleaving equivalences, and also the
equivalences based on steps (multisets of concurrently
executed actions) are not preserved by refinement of
actions. We prove that "linear time" partial order
semantics, where causality in runs is explicit, is
invariant under refinement. Finally, we consider various
bisimulation equivalences based on partial orders and show
that the strongest one of them is preserved by refinement
whereas the others are not.
Keywords: Concurrency, event structures, semantic equivalences,
interleaving vs. partial orders, bisimulation, action refinement.
Note: This material is also included in
20 and in 41.
 Arbeitspapiere der GMD 366, Sankt Augustin, Germany 1989.
 Appeared in Chapter VI of my Ph.D. Thesis.
 Extended abstract in: Proceedings Mathematical Foundations
of Computer Science 1989 (MFCS), PoræbkaKozubnik, Poland,
August/September 1989 (A. Kreczmar & G. Mirkowska, eds.),
LNCS 379, SpringerVerlag, 1989, pp. 237248.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#10
In comparative concurrency semantics, one usually
distinguishes between linear time and branching time
semantic equivalences. Milner's notion of observation
equivalence is often mentioned as the standard example of a
branching time equivalence. In this paper we investigate
whether observation equivalence really does respect the
branching structure of processes, and find that in the
presence of the unobservable action tau of CCS this is not
the case.
Therefore the notion of branching bisimulation equivalence
is introduced which strongly preserves the branching
structure of processes, in the sense that it preserves
computations together with the potentials in all
intermediate states that are passed through, even if silent
moves are involved. On closed terms, branching bisimulation
can be completely axiomatized by the two laws:
x;tau = x
x;((tau;(y+z))+y) = x;(y+z).
For a large class of processes it turns out that branching
bisimulation and observation equivalence are the same. All
protocols known to the authors that have been verified in
the setting of observation equivalence happen to fit in
this class, and hence are also valid in the stronger
setting of branching bisimulation equivalence.
Keywords: Concurrency, process algebra, semantic equivalences,
abstraction, branching time, bisimulation.
Note: This is an extended abstract of 23.
 CWI report CSR8911
 Appeared in Chapter III of my Ph.D. Thesis.
 In: Information Processing 89, Proceedings of the IFIP 11th
World Computer Congress, San Francisco, USA 1989 (G.X.
Ritter, ed.), Elsevier Science Publishers B.V. (North
Holland), 1989, pp. 613618.
In this paper we consider branching time semantics for
finite sequential processes with silent moves. We show that
Milner's notion of observation equivalence is not preserved
under refinement of actions, even when no interleaving
operators are considered; however the authors' notion of
branching bisimulation is.
Keywords: Concurrency, process algebra, semantic equivalences,
abstraction, branching time, bisimulation, action refinement.
Note: This paper is included in 23.
 CWI report CSR8922
 Appeared as Section 6 of Chapter III of my
Ph.D. Thesis.
 In: J.W de Bakker, 25 jaar semantiek, liber amicorum,
Centre for Mathematics and Computer Science, Amsterdam
1989, pp. 247252;
 and in: Proceedings AMAST Conference,
Iowa City, USA 1989, pp. 197201.
The domain of De Bakker and Zucker processes is the unique
complete metric space (up to isometry) satisfying a
reflexive domain equation for metric spaces. We give a
straightforward translation from image finite labelled
transition systems to processes in this domain, such that
two labelled transition systems are bisimilar iff they
translate to the same process. The isometries in this
translation can be dispensed with after selecting a
canonical representative of the metric domain within Aczel's
universe of nonwellfounded sets. Then the translation
generalizes to systems which are not required to be image
finite, in which case it may yield processes outside the
metric space however.
Keywords: Concurrency, labelled transition systems, bisimulation, domain
equations, metric space, fixed points, nonwellfounded sets.
 In: J.W de Bakker, 25 jaar semantiek, liber amicorum,
Centre for Mathematics and Computer Science, Amsterdam
1989, pp. 243246.
In this note we argue:
 that there are several semantic equivalences based on
partial orders which are not preserved by action refinement
(namely when taking the choice structure of systems into account);
 that nevertheless a "branching time" partial order
equivalence can be found that is preserved under refinement;
 but that, in order to achieve preservation under refinement
it is not necessary to employ partial order semantics:
there exists equivalences that abstract from the causal
structure of concurrent systems and are still preserved
under refinement.
Keywords: Concurrency, Petri nets, semantic equivalences,
interleaving vs. partial orders, bisimulation, action
refinement.
Note: This is an informal summary of 10 and 15, using Petri nets instead of event structures.
 CWI note CSN8901
 Appeared as Chapter V of my Ph.D. Thesis.
 Bulletin of the EATCS 38, 1989, pp. 154163.
In this paper I prove that STbisimulation equivalence, as
introduced in 6, is preserved under
refinement of actions.
This implies that it is possible to abstract from the
causal structure of concurrent systems without assuming
action atomicity.
Keywords: Concurrency, event structures, semantic equivalences,
interleaving vs. partial orders, bisimulation, action refinement.
 CWI report CSR9002.

Available as scanned pdf file.
 Appeared as Chapter VII of my Ph.D. Thesis.
 In: Programming Concepts and Methods, Proceedings of a IFIP
Working Group 2.2/2.3 Working Conference, Sea of Galilee,
Israel, 25 April 1990 (M. Broy & C.B. Jones, eds.),
Elsevier Science Publishers B.V. (NorthHolland), 1990, pp.
2752.
We consider an operator for refinement of actions to be
used in the design of concurrent systems. Actions on a
given level of abstraction are replaced by more complex
processes on a lower level. This is done in such a way that
the behaviour of the refined system may be inferred
compositionally from the behaviour of the original system
and from the behaviour of the processes substituted for
actions. We define this refinement operation for causality
based models like event structures and Petri nets. For
Petri nets, we relate it to other approaches for refining
transitions.
Keywords: Concurrency, Petri nets, event structures,
action refinement.
Note: This paper is included in 41.
 Arbeitspapiere der GMD 428, Sankt Augustin, Germany 1990.
 Appeared as Chapter IV of my Ph.D. Thesis.
 In: Stepwise Refinement of Distributed Systems: Models,
Formalism, Correctness, Proceedings REX Workshop, Mook, The
Netherlands, May/June 1989 (J.W. de Bakker, W.P. de Roever
& G. Rozenberg, eds.), LNCS 430, SpringerVerlag, 1990,
pp. 267300.
Keywords: Concurrency, process algebra, ACP, modular algebraic
specifications, communication protocols, semantic equivalences,
linear time, branching time, abstraction, bisimulation,
labelled transition systems, event structures, Petri nets,
interleaving vs. partial orders, action refinement
Note: This thesis combines the material of 19,
7, 11, 12, 23, 16, 14, 10, 20 and 15.
We introduce three models of probabilistic processes,
namely, reactive, generative, and stratified. These models
are investigated within the context of PCCS, a dialect of
Milner's SCCS in which each summand of a process summation
expression is guarded by a probability and the sum of these
probabilities is 1. For each model we present an operational
semantics of PCCS and a notion of bisimulation equivalence
which we prove to be a congruence. We also show that the
models form a hierarchy: the reactive model is derivable from
the generative model by abstraction of the relative
probabilities of different actions, and the generative model
is derivable from the stratified model by abstraction of the
purely probabilistic branching structure.
Keywords: Concurrency, probabilistic processes, SCCS, structural
operational semantics, bisimulation.
Note: This paper is included in 30.
 CWI report CSR9020
 In: Proceedings 5th Annual IEEE Symposium on Logic in
Computer Science, LICS 90, Philadelphia, USA, IEEE
Computer Society Press, Los Alamitos 1990, pp. 130141.
In this paper various semantics in the linear time 
branching time spectrum are presented in a uniform,
modelindependent way. Restricted to the domain of finitely
branching, concrete, sequential processes, only twelve of
them turn out to be different, and most semantics found in
the literature that can be defined uniformly in terms of
action relations coincide with one of these twelve.
Several testing scenarios, motivating these semantics, are
presented, phrased in terms of 'button pushing experiments'
on generative and reactive machines. Finally ten of these
semantics are applied to a simple language for finite,
concrete, sequential, nondeterministic processes, and for
each of them a complete axiomatization is provided.
Keywords: Concurrency, Linear time, Branching time, Button pushing
experiments, Generative machines, Reactive machines,
Bisimulation semantics, Trace semantics, Failure semantics,
Failure trace semantics, Readiness semantics, Ready trace
semantics, Simulation semantics, Ready simulation
semantics, Nondeterminism, Complete axiomatizations.
Note: This paper is included in 43.
 CWI report CSR9029 and TUM report I9025 (i.e. Report
TUMI9025, Technical University of Munich, Munich, Germany
1990) (= SFBBericht Nr. 342/13/90 A).
 Appeared as Chapter I of my Ph.D. Thesis.
 Extended abstract in: Proceedings CONCUR '90, Theories of
Concurrency: Unification and Extension, Amsterdam, The
Netherlands, August 1990 (J.C.M. Baeten & J.W. Klop, eds.),
LNCS 458, SpringerVerlag, 1990, pp. 278297.
Note: This is an extended and updated version of 10.
The extension consists of considering equivalences and
refinement for the domain of flow event structures
— instead of the subdomain of prime event structures —
and allowing also infinite refinements and refinements with
conflict. This paper is included in 41.
Keywords: Concurrency, event structures, semantic equivalences,
interleaving vs. partial orders, bisimulation, action refinement.
 TUM report I9024 (= SFBBericht Nr. 342/12/90 A).
 An earlier version appeared as Chapter VI of my Ph.D. Thesis.
 In: Semantics of Systems of Concurrent Processes,
Proceedings LITP Spring School on Theoretical Computer
Science, La RochePosay, France, April 1990 (I.
Guessarian, ed.), LNCS 469, SpringerVerlag, 1990, pp.
309333.
We consider flow event structures as a model for concurrent
systems. They are suited for defining a compositional
refinement operation, replacing actions in system
descriptions on a higher level by more complex processes on
a lower level. We discuss sequential composition and the
treatment of deadlocks in flow event structures. We propose
an equivalence notion which takes account of deadlocks and
is a congruence for the refinement operator.
Keywords: Concurrency, deadlock, event structures,
semantic equivalences, interleaving vs. partial orders,
bisimulation, action refinement.
Note: This paper is included in 41.
 TUM report I9044 (= SFBBericht Nr. 342/23/90 A).
 Abstract in: Proceedings 3rd
Workshop on Concurrency and Compositionality, Goslar, March
58, 1991 (E. Best & G. Rozenberg, eds.), GMDStudien
Nr. 191, Sankt Augustin, Germany 1991, pp. 113116.
This paper proposes a modular approach to the algebraic
specification of process algebras. This is done by means of
the notion of a module. The simplest modules are building
blocks of operators and axioms, each block describing a
feature of concurrency in a certain semantical setting. These
modules can then be combined by means of a union operator +,
an export operator [], allowing to forget some operators in a
module, an operator H, changing semantics by taking
homomorphic images, and an operator S which takes
subalgebras. These operators enable us to combine modules in
a subtle way, when the direct combination would be
inconsistent. We give a presentation of equational logic,
infinitary conditional equational logic — of which we also
proof the completeness — and first order logic and show how
the notion of a formal proof of a formula from a theory can
be generalized to that of a proof of a formula from a module.
This module logic is then applied in process algebra. We
show how auxiliary process algebra operators can be hidden
when this is needed. Moreover we demonstrate how new process
combinators can be defined in terms of more elementary ones
in a clean way. As an illustration of our approach we specify
some FIFOqueues and verify several of their properties.
Keywords: Concurrency, process algebra, modular algebraic
specifications, export operator, union of modules,
homomorphism operator, subalgebra operator, FIFOqueues,
chaining operator
Note: This is a substantial revision of part of 7.
This revision
intends to be an improvement; however, for more applications
of our module approach, e.g. to the specification of more
curious queues and to the verification of the concurrent
alternating bit protocol, as well as for the treatment of
manysorted module logic, we refer to the old version.
See 11 and 12. Moreover the
differences and similarities between branching
bisimulation, taubisimulation (weak bisimulation,
observation equivalence), etabisimulation (see
3) and delay bisimulation are investigated.
Besides branching bisimulation with fair abstraction also
branching bisimulation with explicit divergence and a
branching bisimulation preorder are introduced. Complete
axiomatizations of branching bisimulation on closed BPA,
CCS and ACPterms are provided. Whereas CCS has only
action prefixing, BPA and ACP have general sequential
composition; but only ACP distinguishes between deadlock
and successful termination. For CCS the axiomatization
consists of the single axiom scheme
a.((tau.(y+z))+y) = a.(y+z)
(where a ranges over all actions) and the usual laws of
strong congruence.
Keywords: Concurrency, process algebra, semantic equivalences,
abstraction, branching time, bisimulation, action
refinement, divergence, deadlock, termination, tick.
Note: This paper properly contains 11 and 12. An updated
version appeared in
JACM 43(3), 1996, pp. 555600.
 TUM report I9052 (= SFBBericht
Nr. 342/29/90 A) and CWI report CSR9120.
 Appeared as Chapter III of my Ph.D. Thesis.
 Updated version in the
Journal of the ACM 43(3), 1996, pp. 555600.
 Free download from the ACM (4.2MB):
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#23
This message defines higher dimensional automata, a notion
of (history preserving) bisimulation between them, directed
homotopy between paths in an HDA, and the unfolding of HDA.
Keywords: Higher dimensional automata, cubical sets,
(history preserving) bisimulation, homotopy, unfolding.
We investigate how to restrict the concept of action
refinement such that established interleaving equivalences
for concurrent systems are preserved under these restricted
refinements. We show that interleaving bisimulation is preserved
under refinement if we do not allow to refine action occurrences
deciding choices and action occurrences involved in autoconcurrency.
On the other hand, interleaving trace equivalence is still not
preserved under these restricted refinements.
Keywords: Concurrency, event structures, semantic equivalences,
interleaving vs. partial orders, bisimulation, action
refinement, atomicity.
This paper offers a complete inference system for branching
bisimulation congruence on a basic sublanguage of CCS for
representing regular processes with silent moves. Moreover,
complete axiomatizations are provided for the guarded
expressions in this language, representing the
divergencefree processes, and for the recursionfree expressions,
representing the finite processes. Furthermore it is argued
that in abstract interleaving semantics (at least for finite
processes) branching bisimulation congruence is the finest
reasonable congruence possible. The argument is that for
closed recursionfree process expressions, in the presence
of some standard process algebra operations like partially
synchronous parallel composition and relabelling, branching
bisimulation congruence is completely axiomatized by the
usual axioms for strong congruence together with Milner's
first taulaw.
Keywords: Concurrency, regular processes, branching bisimulation,
CCS, structural operational semantics, recursion, complete
axiomatizations.
 Report No. STANCS931470, Department of computer Science,
Stanford University, CA 94305, USA.
 Available at
http://rvg.web.cse.unsw.edu.au/pub/complete.dvi.gz (also as
tex,
ps
and pdf).
 In: Proceedings Mathematical Foundations of Computer
Science 1993 (MFCS), Gdansk, Poland, August/September 1993
(A.M. Borzyszkowski & S. Soko
lowski,
editors.), LNCS 711, SpringerVerlag, 1993, pp. 473484.
This paper studies semantic equivalences and preorders for
sequential systems with silent moves, restricting attention
to the ones that abstract from successful termination,
stochastic and realtime aspects of the investigated
systems, and the structure of the visible actions systems
can perform. It provides a parameterized definition of
such a preorder, such that most such preorders and
equivalences found in the literature are obtained by a
suitable instantiation of the parameters. Other
instantiations yield preorders that combine properties from
various semantics. Moreover, the approach shows several
ways in which preorders that were originally only
considered for systems without silent moves, most notably
the ready simulation, can be generalized to an
abstract setting. All preorders come withor rather
asa modal characterization, and when possible also a
relational characterization. Moreover they are motivated by
means of an (also parameterized) testing scenario, phrased
in terms of 'button pushing experiments' on generative and
reactive machines. The testing scenarios for branching
bisimulation, etabisimulation and coupled simulation and
the corresponding modal characterizations are especially new.
Keywords: Concurrency, Labelled transition systems, Nondeterminism,
Abstraction, Divergence, Underspecification, Liveness, Fairness,
Recursion, Semantic equivalences, Linear time, Branching time,
Generative and reactive systems, Button pushing experiments,
May and must preorders, Modal Characterizations, Relational
Characterizations, Trace semantics, Failure semantics, Failure
trace semantics, Readiness semantics, Ready trace semantics,
Simulation, Ready simulation, Stable bisimulation, Contrasimulation,
Coupled simulation, Weak and branching bisimulation.
The concept of branching time in the semantics of
concurrent systems is well known and well understood. Still
a formal definition of what it means for a model or
equivalence to respect branching time has never explicitly
be given. This note proposes such a definition.
Additionally the opportunity is taken to voice an old but
poorly understood argument for using branching time
semantics instead of models or equivalences that are fully
abstract with respect to some notion of observability.
Keywords: Concurrency, semantic equivalences, linear time, branching
time, labelled transition systems, branching bisimulation.
 Report No. STANCS931486
 Available at http://rvg.web.cse.unsw.edu.au/pub/branching.tex.gz,
http://rvg.web.cse.unsw.edu.au/pub/branching.dvi.gz,
http://Boole.stanford.edu/pub/branching.ps.gz,
http://Boole.stanford.edu/pub/branching.pdf.gz and
http://Theory.stanford.edu/~rvg/branching.
 In: The Concurrency Column (M. Nielsen, ed.),
Bulletin of the EATCS 53, June 1994, pp. 190198.
 In: Current Trends in Theoretical Computer Science;
Entering the 21st Century (G. Paun, G. Rozenberg &
A. Salomaa, eds.), World Scientific, 2001, pp. 469479.
This paper explores the connection between semantic
equivalences for concrete sequential processes, represented
by means of transition systems, and formats of transition
system specifications using Plotkin's structural approach.
For several equivalences in the linear time – branching
time spectrum a format is given, as general as possible,
such that this equivalence is a congruence for all
operators specifiable in that format. And for several
formats it is determined what is the coarsest congruence
with respect to all operators in this format that is finer
than partial or completed trace equivalence.
Keywords: Concurrency, structural operational semantics, labelled
transition systems, semantic equivalences.
Note: This is an extended abstract of material that has
been elaborated in 33, 48,
and a paper yet to be written.
 Available at
http://Boole.stanford.edu/pub/sos.ps.gz. Also as
pdf.
 In: Proceedings of the Third International Conference on
Algebraic Methodology and Software Technology (AMAST'93),
Twente, The Netherlands, June 1993, (M. Nivat, C. Rattray,
T. Rus & G. Scollo, eds.), Workshops in Computing,
SpringerVerlag, 1993, pp. 7582.
A simple ST operational semantics for a process algebra is
provided, by defining a set of operational rules in
Plotkin's style. This algebra comprises TCSP parallel
composition, ACP sequential composition and a refinement
operator, which is used for replacing an action with an
entire process, thus permitting hierarchical specification
of systems. We prove that STbisimulation equivalence is a
congruence, resorting to standard techniques on rule
formats. Moreover, we provide a set of axioms that is sound
and complete with respect to STbisimulation. The
intriguing case of the forgetful refinement (i.e., when an
action is refined into the properly terminated process) is
dealt with in a new, improved manner.
Keywords: Concurrency, complete axiomatizations, labelled
transition systems, structural operational semantics,
bisimulation, action refinement, empty process, termination
 Technical Report UBLCS9326, Laboratory for Computer
Science, University of Bologna
 Available at
ftp://ftp.cs.unibo.it/pub/TR/UBLCS/1993/9326.ps.gz and
http://rvg.web.cse.unsw.edu.au/pub/axiomst.dvi.gz (also as
tex,
ps
and pdf).
 In: Proceedings IFIP Working Conference on Programming
Concepts, Methods and Calculi, San Miniato, Italy, June 1994
(E.R. Olderog, ed.), Elsevier Science Publishers B.V.
(NorthHolland), 1994, pp. 169188.
We introduce three models of probabilistic processes, namely,
reactive, generative and stratified. These models are investigated
within the context of PCCS, an extension of Milner's SCCS
in which each summand of a process summation expression is
guarded by a probability and the sum of these probabilities
is 1. For each model we present a structural operational
semantics of PCCS and a notion of bisimulation equivalence
which we prove to be a congruence. We also show that the
models form a hierarchy: the reactive model is derivable from
the generative model by abstraction of the relative
probabilities of different actions, and the generative model
is derivable from the stratified model by abstraction of the
purely probabilistic branching structure. Moreover the
classical nonprobabilistic model is derivable from each of
these models by abstraction from all probabilities.
Keywords: Concurrency, probabilistic processes, SCCS, structural
operational semantics, semantic equivalences, bisimulation.
Note: This paper properly contains 18.
De Simone showed that a wide class of languages, including
CCS, SCCS, CSP and ACP, are expressible up to strong
bisimulation equivalence in Meije. He also showed that every
recursively enumerable process graph is representable by a
Meije expression. Meije in turn is expressible in aprACP
(ACP with action prefixing instead of sequential composition).
Vaandrager established that both results crucially depend
on the use of unguarded recursion, and its noncomputable
consequences. Effective versions of CCS, SCCS, Meije and ACP,
not using unguarded recursion, are incapable of expressing all
effective De Simone languages. And no effective language can
denote all computable process graphs.
In this paper I recreate De Simone's results in aprACP
without using unguarded recursion. The price to be payed for
this is the use of a partial recursive communication function
and—for the second result—a single constant denoting a
simple infinitely branching process. Due to the noncomputable
communication function, the version of aprACP employed is
still not effective.
However, I also define a wide class of De Simone languages
that are expressible in an effective version of aprACP. This
class includes the effective versions of CCS, SCCS, ACP, Meije
and most other languages proposed in the literature, but not
CSP. An even wider class, including CSP, turns out to be
expressible in an effective version of aprACP to which an
effective relational renaming operator has been added.
Keywords: Concurrency, process algebra, ACP, Meije, CCS, CSP, SCCS,
CCSP, relational relabelling, labelled transition systems,
structural operational semantics, bisimulation.
 Available as
pdf,
dvi,
ps and
tex source.
 In: ACP94, Workshop on Algebra of Communicating Processes,
Utrecht, The Netherlands, May 1994, (A. Ponse, C. Verhoef &
S.F.M. van Vlijmen, eds.), Workshops in
Computing, SpringerVerlag, 1994, pp. 188217.
 Draft full version available on request.
This paper reviews several methods to associate transition
relations to transition system specifications with negative
premises in Plotkin's structural operational style. Besides
a formal comparison on generality and relative consistency,
the methods are also evaluated on their taste in determining
which specifications are meaningful and which are not.
Keywords: Structural operational semantics, logic programming,
negative premises, negation as failure.
Note: A mild revision with added emphasis on 3valued
interpretations appeared as 53.
 Report
STANCSTN9516
 Available at
http://rvg.web.cse.unsw.edu.au/pub/negative.dvi.gz (also as
tex,
ps,
pdf and
gif).
 Extended abstract in: Automata, Languages and Programming,
Proceedings 23th International Colloquium, ICALP '96,
Paderborn, Germany, July 1996 (F. Meyer auf der Heide &
B. Monien, eds.), LNCS 1099, Springer, 1996, pp. 502513.
 Extended abstract available as
dvi,
tex,
ps
and pdf.
 A mild revision with added emphasis on 3valued
interpretations appeared as 53.
Groote and Vaandrager introduced the tyft/tyxt format
for Transition System Specifications (TSSs), and established
that for each TSS in this format that is wellfounded, the
bisimulation equivalence it induces is a congruence. In this paper,
we construct for each TSS in tyft/tyxt format an equivalent
TSS that consists of tree rules only. As a corollary we can
give an affirmative answer to an open question, namely whether the
wellfoundedness condition in the congruence theorem for tyft/tyxt
can be dropped. These results extend to tyft/tyxt with negative
premises and predicates.
Keywords: Concurrency, labelled transition systems,
structural operational semantics, bisimulation.
Configuration structures provide a model of concurrency
generalising the families of configurations of event structures.
They can be considered logically, as classes of propositional
models; then subclasses can be axiomatised by formulae of simple
prescribed forms. Several equivalence relations for event
structures are generalised to configuration structures, and also
to general Petri nets. Every configuration structure is shown to
be STbisimulation equivalent to a prime event structure with
binary conflict; this fails for the tighter history preserving
bisimulation. Finally, Petri nets without selfloops under the
collective token interpretation are shown behaviourally
equivalent to configuration structures, in the sense that there
are translations in both directions respecting history preserving
bisimulation. This fails for nets with selfloops.
Keywords: Concurrency, Configuration structures, Event structures,
Petri nets, Semantic equivalences, Bisimulation.
35.
The difference between splitting in n and n+1
R.J. van Glabbeek (Stanford) & F.W. Vaandrager (CWI)
July 1995
It is established that durational and structural aspects of
actions can in general not be modeled in interleaving
semantics, even when timeconsuming actions are represented
by pairs of instantaneous actions denoting their start and
finish. By means of a series of counterexamples it is shown
that, for any n, it makes a difference whether actions are
split in n or in n+1 parts.
Owl example:
*
/ \
1 2
/ \
* *
/ \ / \
0 2 1 0
/  \ / @ \
* * *
\ / \ /
,*. 2 0 0 1 ,*.
,0' `2.\ / \ /,1' `0.
.*' `* `' *' `*.
,1' `2. ,0'/ \ / \`0. ,1' `2.
*' `*' 1 0 0 2 `*' ,*
`2. ,1' / \ / \ `2. ,1'
`*' * * * `*'
\ / \ /
0 1 2 0
\ / \ /
* *
\ /
2 1
\ /
*
Keywords: Concurrency, pomsets, event structures, process graphs,
semantic equivalences, interleaving vs. partial orders,
bisimulation, realtime consistency, action refinement, splitting.
 Report CSR9553, CWI, Amsterdam.
 Updated version, January 1997, available at
http://boole.stanford.edu/pub/split.pdf.

Information and Computation 136(2), 1997, pp. 109142.
 Abstract in: Proceedings 3rd
Workshop on Concurrency and Compositionality, Goslar, March
58, 1991 (E. Best & G. Rozenberg, eds.), GMDStudien
Nr. 191, Sankt Augustin, Germany 1991, pp. 117121.
In this paper I argue that, contrary to what is widely
believed, process graphs, or labelled transition systems,
have enough structure to model noninterleaved features of
concurrency.*
To this end I introduce a class of process graphs obeying
the restriction that any state not only uniquely
characterizes the future of a concurrent behaviour, but
also its concurrent history. These history preserving
process graphs capture branching time,
conjunctive (partial order) causality and
disjunctive causality, just like Winskel's event
structures, as well as phenonema like resolved
conflict that can not be modelled by event structures.
They generalize the Scott domains which arise as the duals
of general event structures and can be regarded as a step
towards a geometric model of concurrency.
Keywords: Concurrency, Process graphs, Event automata,
Configuration structures, Event structures, Causality.
It is shown that the analysis of weak congruence can
sometimes be simplified by means of a similar analysis of
branching congruence as an intermediate step. This point is
made through a completeness proof for an equational
axiomatization of basic CCS with prefix iteration.
Keywords: Concurrency, process algebra, complete axiomatizations,
weak and branching bisimulation, prefix iteration.
Prefix iteration is a variation on the original binary version of
the Kleene star operation P*Q, obtained by restricting the
first argument to be an atomic action. The interaction of prefix
iteration with silent steps is studied in the setting of Milner's
basic CCS. Complete equational axiomatizations are given for four
notions of behavioural congruence over basic CCS with prefix
iteration, viz. branching congruence, etacongruence, delay
congruence and weak congruence. The completeness proofs for eta,
delay, and weak congruence are obtained by reduction to the
completeness theorem for branching congruence. It is also argued
that the use of the completeness result for branching congruence in
obtaining the completeness result for weak congruence leads to a
considerable simplification with respect to the only direct proof
presented in the literature. The preliminaries and the completeness
proofs focus on open terms, i.e., terms that may contain process
variables. As a byproduct, the omegacompleteness of the
axiomatizations is obtained as well as their completeness for closed
terms.
Keywords: Concurrency, process algebra, basic CCS,
prefix iteration, branching bisimulation,
etabisimulation, delay bisimulation, weak bisimulation,
equational logic, complete axiomatizations.
Translations between several models of concurrency are reviewed cq.
proposed. The models considered capture causality and branching time
(and their interplay) and this behaviour is preserved by the translations.
Keywords: Concurrency, Petri nets, event structures, configuration structures,
Scott domains, propositional theories, labelled transition systems,
history preserving process graphs, higher dimensional automata,
causality, branching time, individual vs. collective token
interpretation of nets.
Flat iteration is a variation on the original binary version
of the Kleene star operation P*Q, obtained by restricting the
first argument to be a sum of atomic actions. It generalizes
prefix iteration, in which the first argument is a single
action. Complete finite equational axiomatizations are given
for five notions of bisimulation congruence over basic CCS
with flat iteration, viz. strong congruence, branching
congruence, etacongruence, delay congruence and weak
congruence. Such axiomatizations were already known for prefix
iteration and are known not to exist for general iteration.
The use of flat iteration has two main advantages over prefix
iteration:
 The current axiomatizations generalize to full CCS, whereas
the prefix iteration approach does not allow an elimination
theorem for an asynchronous parallel composition operator.
 The greater expressiveness of flat iteration allows for
much shorter completeness proofs.
In the setting of prefix iteration, the most convenient way to
obtain the completeness theorems for eta, delay, and weak
congruence was by reduction to the completeness theorem for
branching congruence. In the case of weak congruence this
turned out to be much simpler than the only direct proof
found. In the setting of flat iteration on the other hand, the
completeness theorems for delay and weak (but not eta)
congruence can equally well be obtained by reduction to the
one for strong congruence, without using branching congruence
as an intermediate step. Moreover, the completeness results
for prefix iteration can be retrieved from those for flat
iteration, thus obtaining a second indirect approach for
proving completeness for delay and weak congruence in the
setting of prefix iteration.
Keywords: Concurrency, process algebra, CCS, flat iteration,
strong bisimulation, branching bisimulation, etabisimulation,
delay bisimulation, weak bisimulation, complete axiomatizations.
 Report
STANCSTN9757, Department of Computer Science,
Stanford University, CA 94305, USA 1997.
 Available at
http://rvg.web.cse.unsw.edu.au/pub/flat.dvi.gz (also as
tex,
pdf,
A4.ps and
US.ps).
 Archived at http://arxiv.org/abs/cs/9810008.
 In: Proceedings CONCUR '97, Warsaw, Poland, July 1997
(A. Mazurkiewicz & J. Winkowski, eds.), LNCS 1243,
Springer, 1997, pp. 228242.
In this talk I consider mappings from expressions in system
description languages like CCS and CSP to Petri nets and vice versa.
I recall two methods for associating a Petri net to such a process
expression: the standard compositional approach where recursion is
dealt with using fixed point techniques, and a variant due to Ursula
Goltz in which recursion is implemented by redirecting arcs backwards
to initial places. The former approach always yields a socalled safe
flow net; recursion typically gives rise to infinite nets. The latter
approach works for the subclass of process expressions where in the
scope of a recursion construct only prefixing, independent parallel
composition and guarded choice is allowed; but always yields finite
S/Tnets. The two approaches are identical for recursionfree process
expressions; in general they agree up to fully concurrent bisimulation
equivalence. Here I extend the latter approach to deal with unguarded
recursion. I also show that for every finite S/Tnet there exists a
process expression in the mentioned subclass whose semantics, up to
fully concurrent bisimulation, is that net. Moreover, every finite
safe flow net is denoted up to eventstructure isomorphism by a
recursionfree process expression.
Keywords: Concurrency, Petri nets, process algebra, CCS, CSP,
denotational semantics,recursion, fully concurrent bisimulation.
Computing Natural Language pursues the recent upsurge of research
along the interface of logic, language, and computation, with
applications to artificial intelligence and machine learning. It
contains a variety of contributions to the logical and computational
analysis of natural language. A wide range of logical and
computational tools are employed, and applied to such varied areas as
contextdependency, linguistic discourse, and formal grammar.
This volume is a collection of papers illustrating stateoftheart
interdisciplinary research connecting logic, language, computation and
AI. The papers in this volume deal with contextdependency from
philosophical, computational, and logical points of view; a logical
framework for combining dynamic discourse semantics and preferential
reasoning in AI; negative polarity items in connection with affective
predicates; HeadDriven Phrase Structure Grammar from a perspective of
type theory and category theory; and an axiomatic theory of machine
learning of natural language, with applications to physics word problems.
Keywords: Logic, Language, Computation, Philosophy,
Artificial Intelligence, Context, Indexicals, Unarticulated
Constituents, Discourse, Modal Logic, Dynamic Logic,
Nonmonotonic Logic, Polarity, Monotonicity, Headdriven
Phase Structure Grammar, Type Theory, Universality, Machine
Learning, Physics Word Problems.
March 1998; updated December 1998
The goal of this paper is to develop an algebraic theory of
process scheduling. We specify a syntax for denoting processes composed
of actions with given durations. Subsequently, we propose axioms for
transforming any specification term of a scheduling problem into a term
of all valid schedules. Here a schedule is a process in which all
(implementational) choices (e.g. precise timing) are resolved. In
particular, we axiomatize an operator restricting attention to the
efficient schedules. These schedules turn out to be representable
as trees, because in an efficient schedule actions start only at time
zero or when a resource is released, i.e. upon termination of the action
binding a required resource. All further delay would be
useless. Nevertheless, we do not consider resource constraints
explicitly here. We show that a normal form exists for every term of the
algebra and establish soundness of our axiom system with respect to a
schedule semantics, as well as completeness for efficient processes.
Keywords: Scheduling, efficiency, time, GANTT chart.
 Original version:
Arbeitsberichte des Instituts für Wirtschaftsinformatik
12, Universität KoblenzLandau, Germany 1998.
 Java applet,
bringing SA terms into normal form.
 Updated
version:
Report
STANCSTN9887, Department of Computer Science,
Stanford University, CA 94305, USA 1998.
Available as postscript and PDF.
 Also available at
http://Boole.stanford.edu/pub/sa.ps.gz and at
http://Boole.stanford.edu/pub/sa.pdf.gz.
The postscript file may not be readable with old
versions of ghostview; however, it should print fine.
 Slightly condensed version of the latter in:
Proceedings of the Seventh International Conference on
Algebraic Methodology and Software Technology (AMAST '98),
Amazonia, Brazil, January 1999 (A.M. Haeberer, ed.),
LNCS 1548, Springer, 1999, pp. 278292.
We study an operator for refinement of actions to be used in
the design of concurrent systems. Actions on a given level
of abstraction are replaced by more complicated processes on
a lower level. This is done in such a way that the behaviour
of the refined system may be inferred compositionally from
the behaviour of the original system and from the behaviour
of the processes substituted for actions. We recall that
interleaving models of concurrent systems are not suited for
defining such an operator in its general form. Instead, we
define this operator on several causality based, event
oriented models, taking into account the distinction between
deadlock and successful termination. Then we investigate the
interplay of action refinement with abstraction in terms of
equivalence notions for concurrent systems, considering both
linear time and branching time approaches. We show that
besides the interleaving equivalences, also the equivalences
based on steps are not preserved under refinement of
actions. We prove that linear time partial order semantics
are invariant under refinement. Finally we consider various
bisimulation equivalences based on partial orders and show
that the finest two of them are preserved under refinement
whereas the others are not. Termination sensitive versions
of these equivalences are even congruences for action refinement.
Keywords: Concurrency, action refinement, event structures,
semantic equivalences, interleaving vs. partial orders,
bisimulation, termination, deadlock.
Note: This paper combines and extends the material of
10, 16, 20
and 21, except for the part in 16
on refinement of transitions in Petri nets and the
discussion of TCSPlike parallel composition in 21.
An informal presentation of some basic ingredients of this
paper appeared as 14. Among others, the
treatment of action refinement in stable and nonstable
event structures is new.
In this talk, translations between several models of concurrent
systems are reviewed c.q. proposed. The models considered capture
causality, branching time, and their interplay, and these
features are preserved by the translations. To the extent that
the models are intertranslatable, this yields support for the
point of view that they are all different representations of the
same phenomena. The translations can then be applied to
reformulate any issue that arises in the context of one model
into one expressed in another model, which might be more suitable
for analysing that issue. To the extent that the models are not
intertranslatable, my investigations are aimed at classifying
them w.r.t. their expressiveness in modelling phenomena in
concurrency.
Keywords: Concurrency, Petri nets, configuration structures,
labelled transition systems, higher dimensional automata,
causality, branching time, individual vs. collective token
interpretation of nets.
 Available at
http://rvg.web.cse.unsw.edu.au/pub/concur99.dvi.gz (also as
tex,
ps
and pdf).
 In Proceedings CONCUR '99, 10^{th} International
Conference on Concurrency Theory, Eindhoven, The
Netherlands, August 1999 (J.C.M. Baeten & S. Mauw, eds.),
LNCS 1664, Springer, 1999, pp. 2127.
In this note I argue that the 3rd millennium starts on the the first of
January of the year 2001, rather than on the first of January of the
year 2000.
Keywords: Millennium, calendar, counting.
Keywords: Counting, ordinal numbers, cardinal numbers,
inclusive versus exclusive counting, millennium, calendar.
Keywords: Concurrency, expressiveness.
In this paper various semantics in the linear time  branching
time spectrum are presented in a uniform, modelindependent way.
Restricted to the class of finitely branching, concrete,
sequential processes, only fifteen of them turn out to be
different, and most semantics found in the literature that can be
defined uniformly in terms of action relations coincide with one
of these fifteen. Several testing scenarios, motivating these
semantics, are presented, phrased in terms of 'button pushing
experiments' on generative and reactive machines. Finally twelve
of these semantics are applied to a simple language for finite,
concrete, sequential, nondeterministic processes, and for each of
them a complete axiomatization is provided.
Keywords: Concurrency, Labelled transition systems,
Nondeterminism, Semantic equivalences, Linear time,
Branching time, Generative and reactive systems,
Button pushing experiments, Modal Characterizations,
Relational Characterizations, Trace semantics,
Failures semantics, Failure trace, Ready trace,
Simulation, Ready simulation, Bisimulation, Complete
axiomatizations, Compositionality, Full abstraction,
Renaming, Deadlock, Termination, Sequencing, Recursive
Specification Principle, Nonwellfounded sets.
Note: This is an extension of 19.
Note: The hyperlinks in the above document work perfectly.
In fact, this may very well be the only latex paper ever written with
correct hyperlinks. Here correct is defined as to adhere the hyperref
standard, as advertised on various (changing) websites since the end
of the 20th century. Unfortunately, the latex hyperref package does
not adhere to this standard, even though it was written by the same
people that developed the hyperref standard.
The only document reader I know of that abides by the hyperref
standard, and thus correctly displays the above document, is xdvi.
This reader went out of fashion in the early part of the 21th century,
perhaps exactly because it correctly interpreted the hyperref standard.
If you now use xdvi you really run xdvik, which used
to be a competitor of xdvi that follows the hyperref package
rather than the hyperref standard.
This paper explores the connection between semantic equivalences and
preorders for concrete sequential processes, represented by means of
labelled transition systems, and formats of transition system
specifications using Plotkin's structural approach. For several
preorders in the linear time – branching time spectrum a format
is given, as general as possible, such that this preorder is a
precongruence for all operators specifiable in that format.
The formats are derived using the modal characterizations of the
corresponding preorders.
Keywords: Concurrency, structural operational semantics,
labelled transition systems, semantic equivalences and preorders,
compositionality, full abstraction.
Note: This paper refers for the full proofs to reference [6].
However, that paper turned out to become too large, and has
been split into 48 and the full version of
28.
The current paper is an extended abstract of 48,
except that there we do not include the full abstraction
results mentioned here.
Those results originated from 28 and are
planned to appear in a full version of 28.
Bisimulation equivalence is a semantic equivalence relation on
labelled transition systems, which are used to represent distributed
systems. It identifies systems with the same branching structure.
Keywords: Concurrency, labelled transition systems, modal
logic, Kripke structures, bisimulation, nonwellfounded
sets, abstraction, weak and branching bisimulation.
 Available at
http://rvg.web.cse.unsw.edu.au/pub/bisimulation.dvi.gz
(also as
tex,
ps and
pdf; the source is
tex.pic).
 Originally written for the forgotten Encyclopedia of Distributed
Computing (J.E. Urban & P. Dasgupta, eds.), Kluwer.
 "Further reading" added November 2010. Available as
ps,
pdf,
dvi and
tex file.
 In the
Encyclopedia of Parallel Computing (D. Padua, ed.), Part 2,
Springer, 2011, pp. 136139.
Keywords: Decidability, formal language, algorithms, halting,
enumerability, recognizability
Keyword: undefinable languages.
Flow event structures were introduced as a model
for giving semantics to process algebras. However it turned out
that certain restrictions have to be made to make them suitable
for this purpose. In this paper, we investigate subclasses of flow
event structures which are both suited for the process algebraic
composition operators, and for action refinement as a means of
regarding processes on different levels of abstraction.
First, suitable subclasses are characterised. Then two specific
subclasses are proposed. The larger class generalises the one from
[CZ], which is not suitable for action refinement. The
smaller one is still sufficiently expressive for dealing with all
standard process algebras and action refinement.
Keywords: Concurrency, flow event structures,
parallel composition, action refinement.
D.G. Stork
(Ricoh) & R.J. van Glabbeek (Stanford)
March 2002
We propose extensions to predicate/transition nets to allow
tokens to carry both data and control information, where such
control can refine special "refinable place nodes" in the net.
These formal extensions find use in active document workflow, in
which documents themselves specify portions of the overall
processing within a workflow net. Our approach enables the
workflow designer to specify which places of the target
predicate/transition net may be refined and enables the document
author to specify how these places will be refined (via
attachment of a tokengenerated "refinement net"). This
apportionment of the overall task allows the workflow designer to
set general constraints within which the document author can
control the processing; it prevents conflicts between them in
foreseeable practical cases. Refinable places are augmented with
a permission structure specifying which document authors can
refine that place and which document tokens can execute a node's
refinement net. Our refined nets have a hierarchical structure
which can be represented by bipartite trees.
Keywords: Active document workflow, Petri nets,
hierarchical predicate/transition nets,
tokencontrolled place refinement.
 Available at
http://boole.stanford.edu/pub/token.pdf.gz (also
as
postscript, for previewing only).
 In: Proceedings 23rd International
Conference on Application and Theory of Petri Nets,
Adelaide, Australia, June 2002 (J. Esparza & C. Lakos, eds.),
LNCS,
2360, Springer, 2002, pp. 394413.
This paper explores the connection between semantic equivalences and
preorders for concrete sequential processes, represented by means of
labelled transition systems, and formats of transition system
specifications using Plotkin's structural approach. For several
preorders in the linear time – branching time spectrum a format
is given, as general as possible, such that this preorder is a
precongruence for all operators specifiable in that format.
The formats are derived using the modal characterizations of the
corresponding preorders.
Keywords: Concurrency, structural operational semantics,
labelled transition systems, semantic equivalences and preorders,
compositionality.
Note: This paper subsumes part of the material summarized
in 28. An extended abstract of this paper appeared
as 44, except that in the current paper we do
not include the full abstraction results mentioned there.
Those results originated from 28 and are
planned to appear in a full version of 28.
We address crossorganizational workflows, such as document workflows,
which consist of multiple workflow modules each of which can interact
with others by sending and receiving messages. Our goal is to
guarantee that the global workflow network has properties such as
termination while merely requiring properties that can be checked
locally in individual modules. The resulting query nets are
based on predicate/transition Petri nets and implement formal
constructs for business rules, thereby ensuring such global
termination. Our method does not require the notion of a global
specification, as employed by Kindler, Martens and Reisig.
Keywords: Crossorganizational workflow, Petri nets,
predicate/transition nets, soundness, proper termination,
case independence.
 Available at
http://boole.stanford.edu/pub/query.ps.gz (also as
tex source
and as pdf).
 In:
Proceedings International Conference on Business Process Management,
BPM 2003, Eindhoven, The Netherlands, June 2003
(W.M.P. van der Aalst, A.H.M. ter Hofstede & M. Weske, eds.),
LNCS 2678,
Springer, 2003, pp 184199.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#49
A cornerstone of the theory of proof nets for unitfree
multiplicative linear logic (MLL) is the abstract
representation of cutfree proofs modulo inessential
commutations of rules. The only known extension to additives,
based on monomial weights, fails to preserve this key feature:
a host of cutfree monomial proof nets can correspond to the
same cutfree proof. Thus the problem of finding a
satisfactory notion of proof net for unitfree
multiplicativeadditive linear logic (MALL) has remained open
since the inception of linear logic in 1986. We present a new
definition of MALL proof net which remains faithful to the
cornerstone of the MLL theory.
Keywords: Linear logic, proof nets, additives, cut elimination.
Note: This is an extended abstract of 57.
 A preliminary version of some of the
material in this paper was presented in a talk at
the workshop Linear Logic 2002, Copenhagen.
 In: Proceedings 18th Annual IEEE Symposium on Logic in
Computer Science, LICS 2003, Ottawa, Canada, June 2003, IEEE
Computer Society Press, Los Alamitos 2003, pp. 110.
 Available at
http://Boole.stanford.edu/pub/mallnetslicswithproofs.ps.gz
(also as
tex
and pdf).
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#50
This paper presents a method for the decomposition of HML
formulae. It can be used to decide whether a process
algebra term satisfies a HML formula, by checking whether
subterms satisfy certain formulae, obtained by decomposing
the original formula. The method uses the structural
operational semantics of the process algebra. The main
contribution of this paper is that an earlier decomposition
method from Larsen for the De Simone format is extended to
the more general ntyft/ntyxt format without lookahead.
Keywords: Concurrency, Structural Operational Semantics,
Compositionality, HennessyMilner Logic, Modal Decomposition.
Note: This paper is included in 61.
 Available at
http://rvg.web.cse.unsw.edu.au/pub/hml.dvi.gz (also as
tex,
ps
and pdf).
 In: Proceedings 14th International Symposium on Fundamentals
of Computation Theory, FCT 2003, Malmö, Sweden, August 2003
(A. Lingas & B.J. Nilsson, eds.),
LNCS 2751,
Springer, 2003, pp. 412422.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#51
We investigate which event structures can be denoted by means
of closed CCS + CSP expressions. Working up to isomorphism we
find that
 all denotable event structures are bundle event structures,
 upon adding an infinitary parallel composition all
bundle event structures are denotable,
 without it every finite bundle event structure can be denoted,
 as well as every countable prime event structure with
binary conflict.
Up to hereditary history preserving bisimulation equivalence
finitary conflict can be expressed in terms of binary conflict.
In this setting all countable stable event structures are denotable.
Keywords: Concurrency, event structures, CCSP, expressiveness.
 Available at
http://rvg.web.cse.unsw.edu.au/pub/bundle.dvi.gz (also as
tex,
ps
and pdf).
 In: Proceedings 14th International Conference on Concurrency Theory,
CONCUR 2003, Marseilles, France, September 2003 (R. Amadio & D. Lugiez, eds.),
LNCS 2761,
Springer, 2003, pp. 5771.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#52
This paper reviews several methods to associate transition
relations to transition system specifications with negative
premises in Plotkin's structural operational style. Besides
a formal comparison on generality and relative consistency,
the methods are also evaluated on their taste in determining
which specifications are meaningful and which are not.
Additionally, this paper contributes a proof theoretic
characterisation of the wellfounded semantics for logic
programs.
Keywords: Structural operational semantics, logic programming,
negative premises, negation as failure.
Note: This is a mild revision of 32 with
added emphasis on 3valued interpretations.
In this talk I investigate, in a setting without realtime
or probabilities, which semantical equivalences respect
liveness properties. Many semantics proposed in the literature
do not, which makes them less suitable for verification
purposes. In fact, I argue that in interleaving semantics
liveness properties are preserved only in the presence of global
fairness assumptions. I'll give an overview of the interleaving
semantics that respect liveness, and discuss their complexity
and equational axiomatizations. When global fairness assumptions
are not warranted, noninterleaving semantics are needed to
preserve liveness properties in the presence of a parallel
composition. I speculate about the possibilities in this regard.
Keywords: Concurrency, semantic equivalences, liveness,
progress, fairness, justness, priority, parallel composition,
interleaving semantics, Recursive Specification Principle,
compositionality, impossible futures, realtime consistency,
STfailure trace semantics, complete axiomatizations.
 In: Slide Reprints from the Workshop on Process Algebra:
Open Problems and Future Directions, PA '03, Bologna,
Italy, July 2003 (L. Aceto, Z. Ésik, W.J. Fokkink &
A. Ingólfsdóttir, eds.),
BRICS notes NS033,
Department of Computer Science, University of Aarhus,
Denmark, pp. 5963.
 Available at http://www.cs.auc.dk/~luca/BICI/SLIDESPA03/vanglabbeek.pdf.
This paper studies nested simulation and nested trace
semantics over the language BCCSP, a basic formalism to
express finite process behaviour. It is shown that none of
these semantics affords finite (in)equational axiomatizations
over BCCSP. In particular, for each of the nested semantics
studied in this paper, the collection of sound, closed
(in)equations over a singleton action set is not finitely based.
Keywords: Concurrency, process algebra, BCCSP, nested
simulation, possible futures, nested trace semantics,
equational logic, complete axiomatizations, nonfinitely based
algebras, HennessyMilner logic.
We propose a generalisation of Winskel's event structures, matching
the expressive power of arbitrary Petri nets. In particular, our
event structures capture resolvable conflict, besides disjunctive
and conjunctive causality.
Keywords: Concurrency, Event structures, Petri nets,
Causality, Resolvable conflict.
 Available at
http://rvg.web.cse.unsw.edu.au/pub/resolv.dvi.gz (also as
tex,
ps
and pdf).
 In: Proceedings 29th International Symposium on Mathematical Foundations
of Computer Science (MFCS 2004), Prague, Czech Republic, August 2004
(J. Fiala, V. Koubek & J. Kratochvíl, eds.),
LNCS 3153, Springer, 2004, pp. 550561.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#55
In this paper I compare the expressive power of several models of
concurrency based on their ability to represent causal dependence.
To this end, I translate these models, in behaviour preserving ways,
into the model of higher dimensional automata, which is the most
expressive model under investigation. In particular, I propose four
different translations of Petri nets, corresponding to the four
different computational interpretations of nets found in the
literature.
I also extend various equivalence relations for concurrent systems
to higher dimensional automata. These include the history preserving
bisimulation, which is the coarsest equivalence that fully respects
branching time, causality and their interplay, as well as the
STbisimulation, a branching time respecting equivalence that takes
causality into account to the extent that it is expressible by
actions overlapping in time. Through their embeddings in higher
dimensional automata, it is now welldefined whether members of
different models of concurrency are equivalent.
Keywords: Concurrency, expressiveness, causality, higher
dimensional automata, Petri nets, event structures, history
preserving bisimulation, STbisimulation.
Note: This is an extended abstract of 63.

Electronic Notes in Theoretical Computer Science 128(2),
April 2005: Proceedings of the 11th International Workshop
on Expressiveness in Concurrency, EXPRESS 2004
(J.C.M. Baeten & F. Corradini, eds.), pp. 534.
 My original submission to ENTCS, November 2004, same
content as above, as pdf file.
 Final version, April 2005, available at
http://Boole.stanford.edu/pub/expressea.pdf (also as
tex,
dvi,
and ps).
In footnote 5 this version corrects an error found in the
versions above.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#56
A cornerstone of the theory of proof nets for unitfree multiplicative
linear logic (MLL) is the abstract representation of cutfree proofs
modulo inessential rule commutation. The only known extension to
additives, based on monomial weights, fails to preserve this key
feature: a host of cutfree monomial proof nets can correspond to the
same cutfree proof. Thus the problem of finding a satisfactory
notion of proof net for unitfree multiplicativeadditive linear logic
(MALL) has remained open since the inception of linear logic in 1986.
We present a new definition of MALL proof net which remains faithful
to the cornerstone of the MLL theory.
Keywords: Linear logic, proof nets, additives, cut elimination.
Note: An extended abstract of this paper appeared as
50.
In TCS 146, Bard Bloom presented rule formats for four main notions of
bisimulation with silent moves. He proved that weak bisimulation
equivalence is a congruence for any process algebra defined by WB cool
rules, and established similar results for rooted weak bisimulation
(Milner's "observational congruence"), branching bisimulation and
rooted branching bisimulation. This study reformulates Bloom's results
in a more accessible form and contributes analogues for (rooted)
ηbisimulation and (rooted) delay bisimulation. Moreover,
finite equational axiomatisations of rooted weak bisimulation
equivalence are provided that are sound and complete for finite
processes in any RWB cool process algebra. These require the
introduction of auxiliary operators with lookahead. Finally, a
challenge is presented for which Bloom's formats fall short and
further improvement is called for.
Keywords: Concurrency, structural operational semantics, CCS,
compositionality, branching bisimulation, ηbisimulation,
delay bisimulation, weak bisimulation, complete axiomatizations.
Note: This is an extended abstract of 88.
 Available at
http://rvg.web.cse.unsw.edu.au/pub/coolea.dvi.gz (also as
tex,
ps
and pdf).
© SpringerVerlag Berlin Heidelberg 2005
 In: Proceedings International Colloquium on Theoretical
Aspects of Computing, ICTAC05, Hanoi, Vietnam, October 2005
(D.V. Hung & M. Wirsing, eds.),
LNCS 3722,
Springer, 2005, pp. 318333.
 Submission (same as above but with appendix
for referees, containing the proofs), as
pdf,
ps,
dvi and
tex file.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#58
Starting from the opinion that the standard firing rule of Petri
nets embodies the collective token interpretation of nets rather
than their individual token interpretation, I propose a new
firing rule that embodies the latter. Also variants of both
firing rules for the selfsequential interpretation of nets are
studied. Using these rules, I express the four computational
interpretations of Petri nets by semantic mappings from nets to
labelled step transition systems, the latter being
eventoriented representations of higher dimensional automata.
This paper totally orders the expressive power of the four
interpretations, measured in terms of the classes of labelled
step transition systems up to isomorphism of reachable parts
that can be denoted by nets under each of the interpretations.
Furthermore, I extend the unfolding construction of
place/transition nets into occurrence net to nets that may have
transitions without incoming arcs.
Keywords: Concurrency, Petri nets, higher dimensional automata,
unfolding, expressiveness, causality.
 Available at
http://Boole.stanford.edu/pub/individual.ps.gz (also as
tex,
dvi
and pdf).
© SpringerVerlag Berlin Heidelberg 2005
 In: Proceedings 16th International Conference on
Concurrency Theory, CONCUR 2005, San Francisco, USA, August 2005
(M. Abadi & L. de Alfaro, eds.),
LNCS 3653,
Springer, 2005, pp. 323337.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#59
This paper raises the question on how to specify timeouts
in process algebra, and finds that the basic formalisms
fall short in this task.
Keywords: Concurrency, Process Algebra, Liveness,
Fairness, Timeouts, Priorities, Petri nets.
 Available as
dvi,
ps,
pdf and
tex file.
 In: Short Contributions from the Workshop on
Algebraic Process Calculi: The First Twenty Five Years and
Beyond, PA '05, Bertinoro, Italy, August 2005
(Luca Aceto and Andrew D. Gordon, editors),
BRICS Note NS053,
Department of Computer Science, University of Aarhus,
Denmark 2005, pp. 112113.

Electronic Notes in Theoretical Computer Science 162,
2006, pp. 173175.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#60
This paper presents a method for the decomposition of HML
formulas. It can be used to decide whether a process
algebra term satisfies a HML formula, by checking whether
subterms satisfy certain formulas, obtained by decomposing
the original formula. The method uses the structural
operational semantics of the process algebra. The main
contribution of this paper is the extension of an earlier
decomposition method for the De Simone format from the PhD
thesis of Kim G. Larsen in 1986, to more general formats.
Keywords: Concurrency, Structural Operational Semantics,
Compositionality, HennessyMilner Logic, Modal Decomposition.
Note: This paper properly contains 51.
We present congruence formats for η and rooted
ηbisimulation equivalence. These formats are derived using a
method for decomposing modal formulas in process algebra. To decide
whether a process algebra term satisfies a modal formula, one can
check whether its subterms satisfy formulas that are obtained by
decomposing the original formula. The decomposition uses the
structural operational semantics that underlies the process algebra.
Keywords: Concurrency, Structural Operational Semantics,
Compositionality, Congruence, ηBisimulation,
Modal Logic, Modal Decomposition.
Note: The material of this paper is included in 92.
 Preliminary version in: Participants Proceedings Structural
Operational Semantics 2005, Lisbon, Portugal, June 2005. Available as
dvi,
ps,
pdf and
tex file.
 Final version, October 2005, available as
dvi,
ps,
pdf and
tex file.

Electronic Notes in Theoretical Computer Science 156(1),
May 2006: Proceedings of the Second Workshop on Structural
Operational Semantics, SOS 2005, Lisbon, Portugal
(P. Mosses and I. Ulidowski, eds.), pp. 97113.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#62
In this paper I compare the expressive power of several models of
concurrency based on their ability to represent causal dependence.
To this end, I translate these models, in behaviour preserving ways,
into the model of higher dimensional automata, which is the most
expressive model under investigation. In particular, I propose four
different translations of Petri nets, corresponding to the four
different computational interpretations of nets found in the
literature.
I also extend various equivalence relations for concurrent systems
to higher dimensional automata. These include the history preserving
bisimulation, which is the coarsest equivalence that fully respects
branching time, causality and their interplay, as well as the
STbisimulation, a branching time respecting equivalence that takes
causality into account to the extent that it is expressible by
actions overlapping in time. Through their embeddings in higher
dimensional automata, it is now welldefined whether members of
different models of concurrency are equivalent.
Keywords: Concurrency, expressiveness, causality, higher
dimensional automata, Petri nets, event structures, history
preserving bisimulation, STbisimulation.
Note: An extended abstract of this paper appeared as
56.
 Available at
http://Boole.stanford.edu/pub/express.pdf (also as
tex,
dvi,
and ps).
 Theoretical Computer Science 368(12), 2006, pp. 169194.
 Elsevier did a failed attempt to publish this paper
in
Theoretical Computer Science 356(3), 2006, pp. 265290.
The figures in that publication are mangled.
Elsevier corrected this mistake in Erratum to "On the
expressiveness of higher dimensional automata",
Theoretical Computer Science 368(12), 2006,
pp. 168194. Pages 169194 of this erratum contain the
paper itself, with unmangled figures.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#63
I will compare the expressiveness of several models of
concurrency that could be thought of as formalisations of
higher dimensional automata: cubical sets, presheaves over
a category of bipointed sets, automata with a predicate on
hypercubeshaped subgraphs, labelled step transition
systems, and higher dimensional transition systems. A
series of counterexamples will illustrate the limitations
of each of these models. Additionally I recall a few
results relating higher dimensional automata to ordinary
automata, Petri nets, and various kinds of event structures.
Keywords: Concurrency, expressiveness, causality, higher
dimensional automata, Petri nets, event structures, history
preserving bisimulation.
 In: Preliminary Proceedings of the Workshop on Geometry and
Topology in Concurrency, GETCO '05, San Francisco, USA,
August 2005 (Patrick Cousot, Lisbeth Fajstrup, Eric
Goubault, Maurice Herlihy, Kim G. Larsen & Martin Rauen, eds.)
BRICS Note NS055,
Department of Computer Science, University of Aarhus,
Denmark 2005, page 1.
We present a method for decomposing modal formulas for processes
with the internal action τ. To decide whether a process
algebra term satisfies a modal formula, one can check whether its
subterms satisfy formulas that are obtained by decomposing the
original formula. The decomposition uses the structural
operational semantics that underlies the process algebra.
We use this decomposition method to derive congruence formats
for branching and rooted branching bisimulation equivalence.
Keywords: Concurrency, Structural Operational Semantics,
Compositionality, Congruence, Branching Bisimulation,
Modal Logic, Modal Decomposition.
Note: The material of this paper is included in 92.
 Preliminary report presented at the Fourth International
Symposium on Formal Methods for Components and Objects,
FMCO 2005, Amsterdam, The Netherlands, 3 November 2005.
Available as
dvi,
ps,
pdf and
tex file.
 Final report (hardly different from the above), April 2006,
in Revised Lectures Fourth International Symposium on
Formal Methods for Components and Objects, FMCO '05,
Amsterdam, The Netherlands, November 2005 (F.S. de Boer,
M.M. Bonsangue, S. Graf & W.P. de Roever, eds.), LNCS
4111, Springer, 2006, pp. 195218. Available as
dvi,
ps,
pdf and
tex file.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#64
This paper shows that weak bisimulation congruence can be
characterised as rooted weak bisimulation equivalence, even
without making assumptions on the cardinality of the sets
of states or actions of the processes under consideration.
Keywords: Concurrency, process algebra, process graphs,
weak bisimulation, root condition, Fresh Atom Principle.
Dedication: to Jan Willem Klop,
on the occasion of his 60th birthday.
 Available at
http://Boole.stanford.edu/pub/jwk.ps.gz (also as
tex,
dvi
and pdf).
© SpringerVerlag Berlin Heidelberg 2005
 In: Processes, Terms and Cycles: Steps on the Road to Infinity:
Essays Dedicated to Jan Willem Klop on the Occasion of His
60th Birthday (Aart Middeldorp, Vincent van Oostrom, Femke
van Raamsdonk & Roel de Vrijer, eds.), LNCS 3838,
Springer, 2005, pp. 2639.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#65
Impossible futures equivalence is the semantic equivalence
on labelled transition systems that identifies systems iff
they have the same "AGEF" properties: temporal logic
properties saying that reaching a desired outcome is not
doomed to fail. We show that this equivalence, with an
added root condition, is the coarsest congruence containing
weak bisimilarity with explicit divergence that respects
deadlock/livelock traces (or fair testing, or any liveness
property under a global fairness assumption) and assigns
unique solutions to recursive equations.
Keywords: Concurrency, Process Algebra, Lifeness, Fairness,
AGEF properties, Labelled Transition Systems, Semantic Equivalences,
Recursive Specification Principle.
 Available as
ps,
pdf and
tex file.
 In: Proceedings 17th International Conference on
Concurrency Theory, CONCUR 2006, Bonn, Germany, August 2006
(C. Baier & H. Hermanns, eds.)
LNCS 4137,
Springer, 2006, pp. 126141.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#66
We consider the relational characterisation of branching
bisimilarity with explicit divergence. We prove that it is an
equivalence and that it coincides with the original definition of
branching bisimilarity with explicit divergence in terms of coloured
traces. We also establish a correspondence with several variants of
an actionbased modal logic with until and divergence modalities.
Keywords: Concurrency, labelled transition systems,
modal logic, branching bisimilarity, divergence, coloured traces.
R.J. van Glabbeek (NICTA) & P.D. Mosses (Swansea U.), editors
August 2006
R.J. van Glabbeek (NICTA) & P.D. Mosses (Swansea U.), editors
November 2006
We develop a general testing scenario for probabilistic processes,
giving rise to two theories: probabilistic may testing and
probabilistic must testing. These are applied to a simple
probabilistic version of the process calculus CSP.
We examine the algebraic theory of probabilistic testing, and show
that many of the axioms of standard testing are no longer valid
in our probabilistic setting; even for nonprobabilistic CSP
processes, the distinguishing power of probabilistic tests is much
greater than that of standard tests.
We develop a method for deriving inequations valid in
probabilistic may testing based on a probabilistic
extension of the notion of simulation.
Using this, we obtain a complete axiomatisation for
nonprobabilistic processes subject to probabilistic may testing.
Keywords: Probabilistic processes, nondeterminism, CSP,
transition systems, testing equivalences, simulation,
complete axiomatisations, structural operational semantics.
Dedication: to Gordon Plotkin,
on the occasion of his 60th birthday.

Preliminary report in the original Gordon D. Plotkin
Festschrift (1 copy only) offered to Gordon Plotkin on his
60th birthday.
 Available as
pdf,
ps,
dvi and
tex file.
 In: Computation, Meaning, and Logic: Articles dedicated to
Gordon Plotkin (L. Cardelli, M. Fiore and G. Winskel, eds.),
Electronic Notes in Theoretical Computer Science 172, 2007,
pp. 359397.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#69
The question of equivalence has long vexed research in concurrency,
leading to many different denotational and bisimulationbased
approaches; a breakthrough occurred with the insight that tests
expressed within the concurrent framework itself, based on a
special 'success action', yield equivalences that make only
inarguable distinctions.
When probability was added, however, it seemed necessary to extend the
testing framework beyond a direct probabilistic generalisation in order
to remain useful. An attractive possibility was the extension to
multiple success actions that yielded vectors of
realvalued outcomes.
Here we prove that such vectors are unnecessary when processes
are finitary, that is finitely branching and finitestate:
single scalar outcomes are just as powerful. Thus for finitary
processes we can retain the original, simpler testing approach and its
direct connections to other naturally scalarvalued phenomena.
Keywords: Probabilistic processes, nondeterminism,
probabilistic automata, testing equivalences, reward testing,
hyperplanes, compactness, Markov Decision Processes.
 Available as
pdf and
tex file.
 In: Proceedings 16th European Symposium on Programming,
ESOP 2007, Braga, Portugal, 24 March – 1 April, 2007
(R. De Nicola, ed.),
LNCS 4421,
Springer, 2007, pp. 363378.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#70
In 1992 Wang & Larsen extended the may and must preorders of De
Nicola and Hennessy to processes featuring probabilistic as well as
nondeterministic choice. They concluded with two problems that have
remained open throughout the years, namely to find complete
axiomatisations and alternative characterisations for these preorders.
This paper solves both problems for finite processes with silent
moves. It characterises the may preorder in terms of simulation, and
the must preorder in terms of failure simulation. It also gives a
characterisation of both preorders using a modal logic. Finally it
axiomatises both preorders over a probabilistic version of CSP.
Keywords: Probabilistic processes, nondeterminism, CSP,
transition systems, testing equivalences, simulation,
failure simulation, modal characterisations, complete axiomatisations.
Note: This is an extended abstract of 79.
 Available as
dvi,
ps,
pdf and
tex file.
 In: Proceedings 22nd Annual IEEE Symposium on Logic in
Computer Science, LICS 2007, Wroclaw, Poland, July 2007, IEEE
Computer Society Press, Los Alamitos 2007, pp. 313322.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#71
R.J. van Glabbeek (NICTA) & M. Hennessy (U. Sussex), editors
June 2007
R.J. van Glabbeek (NICTA) & M. Hennessy (U. Sussex), editors
September 2007
We study the equivalence relation on states of labelled transition
systems of satisfying the same formulas in Computation Tree Logic
without the next state modality (CTL_{X}). This relation is
obtained by De Nicola & Vaandrager by translating labelled
transition systems to Kripke structures, while lifting the
totality restriction on the latter. They characterised it
as divergence sensitive branching bisimulation equivalence.
We find that this equivalence fails to be a congruence for
interleaving parallel composition. The reason is that the proposed
application of CTL_{X} to nontotal Kripke structures
lacks the expressiveness to cope with deadlock properties that are
important in the context of parallel composition.
We propose an extension of CTL_{X}, or an
alternative treatment of nontotality, that fills this hiatus.
The equivalence induced by our extension is characterised
as branching bisimulation equivalence with explicit divergence,
which is, moreover, shown to be the coarsest congruence contained
in divergence sensitive branching bisimulation equivalence.
Keywords: Concurrency, temporal logic, Kripke structures,
labelled transition systems, stuttering equivalence,
branching bisimulation, divergence, deadlock.
Although there are many efficient algorithms for calculating the
simulation preorder on finite Kripke structures, only two have been
proposed of which the space complexity is of the same order as the size
of the output of the algorithm. Of these, the one with the best time
complexity exploits the representation of the simulation problem as a
generalised coarsest partition problem. It is based on a fixedpoint
operator for obtaining a generalised coarsest partition as the limit of
a sequence of partition pairs. We show that this fixedpoint theory is
flawed, and that the algorithm is incorrect. Although we do not see how
the fixedpoint operator can be repaired, we correct the algorithm
without affecting its space and time complexity.
Keywords: Concurrency, verification, algorithms,
time and space complexity, simulation preorder, Kripke structures,
generalised coarsest partition problem.
 CSReport 0806, Eindhoven University of Technology, 2008; available as
ps,
pdf and
tex file.
 Extended abstract in: Proceedings 20th International Conference on
Computer Aided Verification (CAV 2008), Princeton, USA, July 2008
(A. Gupta & S. Malik, eds.),
LNCS 5123,
Springer, 2008, pp. 517529.
 Extended abstract available as
ps,
pdf and
tex file.
© SpringerVerlag Berlin Heidelberg 2008
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#74
Determinisation of nondeterministic finite automata is a wellstudied
problem that plays an important role in compiler theory and system
verification. In the latter field, one often encounters automata
consisting of millions or even billions of states. On such input, the
memory usage of analysis tools becomes the major bottleneck. In this
paper we present several determinisation algorithms, all variants of
the wellknown subset construction, that aim to reduce memory usage
and produce smaller output automata. One of them produces automata
that are already minimal. We apply our algorithms to determinise
automata that describe the possible sequences appearing after a
fixedlength run of cellular automaton 110, and obtain a significant
improvement in both memory and time efficiency.
Keywords: Automata, determinisation, minimisation,
algorithms, running time, memory use.
 CSReport 0814, Eindhoven University of Technology, 2008; available as
pdf,
ps and
tex file.
 Extended abstract in: Proceedings Thirteenth International Conference on
Implementation and Application of Automata (CIAA 2008),
San Francisco, California, USA, July 2008 (O.H. Ibarra & B. Ravikumar, eds.),
LNCS 5148,
Springer, 2008, pp. 161170.
 Extended abstract available as
ps,
pdf and
tex file.
© SpringerVerlag Berlin Heidelberg 2008
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#75
R.J. van Glabbeek (NICTA) & P.D. Mosses (Swansea U.), editors
June 2008
We investigate classes of systems based on different interaction patterns
with the aim of achieving distributability. As our system model we use Petri
nets. In Petri nets, an inherent concept of simultaneity is built in, since
when a transition has more than one preplace, it can be crucial that tokens
are removed instantaneously. When modelling a system which is intended to be
implemented in a distributed way by a Petri net, this builtin concept of
synchronous interaction may be problematic. To investigate the problem we
assume that removing tokens from places can no longer be considered as
instantaneous. We model this by inserting silent (unobservable) transitions
between transitions and their preplaces. We investigate three different
patterns for modelling this type of asynchronous interaction. Full
asynchrony assumes that every removal of a token from a place is
time consuming. For symmetric asynchrony, tokens are only removed
slowly in case of backward branched transitions, hence where the concept of
simultaneous removal actually occurs. Finally we consider a more intricate
pattern by allowing to remove tokens from preplaces of backward branched
transitions asynchronously in sequence (asymmetric asynchrony).
We investigate the effect of these different transformations of instantaneous
interaction into asynchronous interaction patterns by comparing the
behaviours of nets before and after insertion of the silent transitions. We
exhibit for which classes of Petri nets we obtain equivalent behaviour with
respect to failures equivalence.
It turns out that the resulting hierarchy of Petri net classes can be
described by semistructural properties. In case of fully symmetric
asynchrony and symmetric asynchrony, we obtain precise characterisations;
for asymmetric asynchrony we obtain lower and upper bounds.
We briefly comment on possible applications of our results to Message
Sequence Charts.
Keywords: Concurrency, Petri nets, distributed systems,
asynchronous interaction, semantic equivalences.
 Technical Report 200803, Technical University of Braunschweig.
 Available as
ps,
pdf and
tex file.
 Archived at http://arxiv.org/abs/0901.0043.
 Extended abstract in: Preproceedings of the
1st
Interaction and Concurrency Experience,
ICE '08: Synchronous and Asynchronous Interactions in Distributed Systems,
Reykjavik, Iceland, July 2008 (F. Bonchi, D. Grohmann, P. Spoletini,
A. Troina & E. Tuosto, eds.), available at
http://ice08.dimi.uniud.it/doku.php?id=ice08:programme.
 Extended abstract in: Proceedings of the
First Interaction and Concurrency Experiences Workshop (ICE 2008),
Reykjavik, Iceland, July 2008 (F. Bonchi, D. Grohmann, P. Spoletini,
A. Troina & E. Tuosto, eds.),
Electronic Notes in Theoretical Computer Science
229(3), 2009, pp. 7795.
 Extended abstract available as
ps,
pdf and
tex file.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#77
When considering distributed systems, it is a central issue how to
deal with interactions between components. In this paper, we
investigate the paradigms of synchronous and asynchronous
interaction in the context of distributed systems. We investigate
to what extent or under which conditions synchronous interaction is
a valid concept for specification and implementation of such
systems. We choose Petri nets as our system model and consider
different notions of distribution by associating locations to
elements of nets. First, we investigate the concept of
simultaneity which is inherent in the semantics of Petri nets when
transitions have multiple input places. We assume that tokens may
only be taken instantaneously by transitions on the same
location. We exhibit a hierarchy of 'asynchronous' Petri net
classes by different assumptions on possible distributions.
Alternatively, we assume that the synchronisations specified in a
Petri net are crucial system properties. Hence transitions and
their preplaces may no longer placed on separate locations. We then
answer the question which systems may be implemented in a
distributed way without restricting concurrency, assuming that
locations are inherently sequential. It turns out that in both
settings we find semistructural properties of Petri nets
describing exactly the problematic situations for interactions in
distributed systems.
Keywords: Concurrency, Petri nets, distributed systems,
reactive systems, asynchronous interaction, semantic equivalences.
 Technical Report 200804, Technical University of Braunschweig.
 Available as
ps,
pdf and
tex file.
 Archived at http://arxiv.org/abs/0901.0048.
 Extended abstract in: Proceedings 33rd International Symposium on
Mathematical Foundations of Computer Science (MFCS 2008),
Toruń, Poland, August 2008 (E. Ochmański & J. Tyszkiewicz, eds.),
LNCS 5162,
Springer, 2008, pp. 1635.
 Extended abstract available as
ps,
pdf and
tex file.
© SpringerVerlag Berlin Heidelberg 2008
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#78
In 1992 Wang & Larsen extended the may and must preorders of De
Nicola and Hennessy to processes featuring probabilistic as well as
nondeterministic choice. They concluded with two problems that have
remained open throughout the years, namely to find complete
axiomatisations and alternative characterisations for these preorders.
This paper solves both problems for finite processes with silent
moves. It characterises the may preorder in terms of simulation, and
the must preorder in terms of failure simulation. It also gives a
characterisation of both preorders using a modal logic. Finally it
axiomatises both preorders over a probabilistic version of CSP.
Keywords: Probabilistic processes, nondeterminism, CSP,
transition systems, testing equivalences, simulation,
failure simulation, modal characterisations, complete axiomatisations.
Note: An extended abstract of this paper appeared as
71.
Recently, Aceto, Fokkink & Ingólfsdóttir proposed an
algorithm to turn any sound and complete axiomatisation of any
preorder listed in the linear time – branching time spectrum at
least as coarse as the ready simulation preorder, into a sound and
complete axiomatisation of the corresponding equivalence—its
kernel. Moreover, if the former axiomatisation is
ωcomplete, so is the latter. Subsequently, de Frutos
Escrig, Gregorio Rodríguez & Palomino generalised this
result, so that the algorithm is applicable to any preorder at
least as coarse as the ready simulation preorder, provided it is
initials preserving. The current paper shows that the same
algorithm applies equally well to weak semantics: the proviso of
initials preserving can be replaced by other conditions, such as
weak initials preserving and satisfying the second τlaw.
This makes it applicable to all 87 preorders surveyed in "the
linear time – branching time spectrum II" that are at least as
coarse as the ready simulation preorder. We also extend the scope
of the algorithm to infinite processes, by adding recursion
constants. As an application of both extensions, we provide a
complete axiomatisation of the CSP failures equivalence for BCCS
processes with divergence.
Keywords: Concurreny, process algebra, BCCS, labelled
transition systems, semantic equivalences and preorders,
equational axiomatisations, ωcompleteness; failures equivalence
We provide a finite basis for the (in)equational theory of the
process algebra BCCS modulo the weak failures preorder and equivalence.
We also give positive and negative results regarding the
axiomatizability of BCCS modulo weak impossible futures semantics.
Keywords: Concurrency, Process Algebra, BCCS, labeled transition systems,
complete axiomatizations, failures semantics, impossible futures semantics.
Note: The material in this paper reappears in 109,
but with rather different proofs.
 Available as
dvi,
ps,
pdf and
tex file.
 Archived at http://arxiv.org/abs/0810.4904.
 Extended abstract in Proceedings 35th Conference on
Current Trends in Theory and Practice of Computer Science,
Špindlerův Mlýn, Czech Republic, January 2009
(M. Nielsen, A. Kucera, P. Bro Miltersen, C. Palamidessi,
P. Tuma & F. Valencia, eds.),
LNCS 5404,
Springer, pp. 167180.
 Extended abstract available as
dvi,
ps,
pdf and
tex file.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#81
In this paper the correspondence between safe Petri
nets and event structures, due to Nielsen, Plotkin and Winskel, is
extended to arbitrary nets without selfloops, under the collective
token interpretation. To this end we propose a more general form of event
structure, matching the expressive power of such nets. These new event
structures and nets are connected by relating both notions with
configuration structures, which can be regarded as
representations of either event structures or nets that capture their
behaviour in terms of action occurrences and the causal relationships
between them, but abstract from any auxiliary structure.
A configuration structure can also be considered logically, as a class
of propositional models, or — equivalently — as a propositional theory
in disjunctive normal from. Converting this theory to conjunctive
normal form is the key idea in the translation of such a structure
into a net.
For a variety of classes of event structures we characterise the
associated classes of configuration structures in terms of their
closure properties, as well as in terms of the axiomatisability of the
associated propositional theories by formulae of simple prescribed
forms, and in terms of structural properties of the associated Petri nets.
Keywords: Concurrency, Configuration structures, Event structures,
Petri nets, Propositional Logic.
Available as
dvi,
ps,
pdf and
tex file.
Archived at http://arxiv.org/abs/0912.4023.
Theoretical Computer Science 410(41) (2009), pp. 41114159,
doi:
10.1016/j.tcs.2009.06.014
This abstract: http://theory.stanford.edu/~rvg/abstracts.html#82
We provide both modal and relational characterisations of may and
musttesting preorders for recursive CSP processes with divergence,
featuring probabilistic as well as nondeterministic choice. May
testing is characterised in terms of simulation, and must testing in
terms of failure simulation. To this end we develop weak transitions
between probabilistic processes, elaborate their topological properties,
and express divergence in terms of partial distributions.
Keywords: Probabilistic processes, nondeterminism, CSP,
transition systems, testing equivalences, simulation,
failure simulation, modal characterisations, divergence.
 Available as
dvi,
ps,
pdf and
tex file.
 In: Proceedings 20th International Conference on Concurrency
Theory, CONCUR 2009, Bologna, Italy, September 2009
(M. Bravetti & G. Zavattaro, eds.),
LNCS 5710, Springer, pp. 274288.
 Draft full version available as
pdf.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#83
Full abstraction for safety and liveness properties
R.J. van Glabbeek (NICTA)
2nd September 2009
If I had to pick just one semantic preorder with a good
scope
of useful applications, I'd say it should be the coarsest
preorder that respects all safety and (conditional) liveness
properties, and is compositional for standard operators such
as hiding and partially synchronous parallel composition.
Such a preorder is called fully abstract.
 Maytesting equivalence is fully abstract for safety properties.
 Must testing is fully abstract for liveness properties
(w.r.t. abstraction, renaming and interleaving) [DH84].
 The maytesting preorder as stated is less useful;
its inverse is fully abstract for safety properties.
 The musttesting preorder is not strong enough.
It is fully abstract for liveness properties but misses out on
conditional liveness properties, which are just as important.
 I present a finer semantics that is fully abstract for safety
and conditional liveness properties w.r.t. abstraction and interleaving.
 I also characterise respect for conditional liveness properties
by means of reward testing,
where positive or negative realvalued rewards can be allocated to
states of testprocesses.
 Due to the use of interleaving operators, musttesting and
related semantics make distinctions
that are wholly unobservable when using merely parallel composition.
 I propose a new semantics that is fully abstract for safety and
(conditional) liveness
properties w.r.t. hiding and parallel composition.
I also reflect on other grounds for selecting particular equivalences
from the the Linear Time – Branching Time Spectrum.
Keywords: Safety properties, liveness properties,
conditional liveness properties, refinement preorders,
labelled transition systems, full abstraction, process algebra,
partially synchronous interleaving operator, parallel composition,
abstraction, may and musttesting preorders, reward testing,
deadlock, livelock, divergence.
Note: Contributions 1–4 were later published as 85.
 Copies of slides. Invited talk for IFIP WG 1.8 at CONCUR 2009 in Bologna.
Available as
pdf.
We consider CSP from the point of view of the algebraic
theory of effects, which classifies operations as effect
constructors or effect deconstructors; it also
provides a link with functional programming, being a refinement of
Moggi's seminal monadic point of view. There is a natural algebraic
theory of the constructors whose free algebra functor
is Moggi's monad; we illustrate this by characterising free and
initial algebras in terms of two versions of the stable failures
model of CSP, one more general than the other. Deconstructors are
dealt with as homomorphisms to (possibly nonfree) algebras.
One can view CSP's action and choice operators as
constructors and the rest, such as concealment and concurrency, as
deconstructors. Carrying this programme out results in taking
deterministic external choice as constructor rather than general
external choice. However, binary deconstructors, such as the CSP
concurrency operator, provide unresolved difficulties. We conclude
by presenting a combination of CSP with Moggi's computational
λcalculus, in which the operators, including concurrency,
are polymorphic. While the paper mainly concerns CSP, it ought to be
possible to carry over similar ideas to other process calculi.
Keywords: Concurrency, functional programming,
computational lambdacalculus, free algebras, (de)constructors,
stable failures model.
Dedication: to Tony Hoare,
in honor of his 75th birthday.
 Available as
dvi,
ps,
pdf and
tex file.
 Archived at http://arxiv.org/abs/1007.5488.
 In: Reflections on the Work of C.A.R. Hoare
(C.B. Jones, A.W. Roscoe & K.R. Wood, eds.), History of
Computing, Springer, 2010, pp. 333369.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#84
This paper characterises the coarsest refinement preorders on labelled
transition systems that are precongruences for renaming and partially
synchronous interleaving operators, and respect all safety, liveness,
and conditional liveness properties, respectively.
Keywords: Safety properties, liveness properties,
conditional liveness properties, refinement preorders,
labelled transition systems, full abstraction, process algebra,
partially synchronous interleaving operator, abstraction,
state operator, deadlock, divergence.
Erratum, 2018: A reference to Lamport has been corrected into one to Alpern & Schneider.
In this paper we work on (bi)simulation semantics of processes that
exhibit both nondeterministic and probabilistic behaviour.
We propose a probabilistic extension of the modal mucalculus and show
how to derive characteristic formulae for various simulationlike
preorders over finitestate processes without divergence.
In addition, we show that even without the fixpoint operators
this probabilistic mucalculus can be used to characterise these
behavioural relations in the sense that two states are equivalent
if and only if they satisfy the same set of formulae.
Keywords: Concurreny, Probabilistic Processes, Modal mucalculus,
simulation, bisimulation, characteristic formulae.
 Available as
dvi,
ps,
pdf and
tex file.
 Archived at http://arxiv.org/abs/1007.5188.
 Extended abstract in: Proceedings 17th International Conference on
Logic for Programming, Artificial Intelligence and Reasoning (LPAR),
Yogyakarta, Indonesia, October 2010 (C.G. Fermüller &
A. Voronkov, eds.), LNCS 6397, Springer, 2010, pp. 278293.
 Extended abstract available as
dvi,
ps,
pdf and
tex file.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#86
We introduce a notion of realvalued reward testing for probabilistic
processes by extending the traditional nonnegativereward testing with
negative rewards. In this richer testing framework, the may and must
preorders turn out to be inverses. We show that for convergent
processes with finitely many states and transitions, but not in the
presence of divergence, the realreward musttesting preorder
coincides with the nonnegativereward musttesting preorder. To prove
this coincidence we characterise the usual resolutionbased testing in
terms of the weak transitions of processes, without having to involve
policies, adversaries, schedulers, resolutions, or similar structures
that are external to the process under investigation. This requires
establishing the continuity of our function for calculating testing
outcomes.
Keywords: Probabilistic processes, nondeterminism, transition systems,
testing equivalences, reward testing, failure simulation, divergence.
Note: This is an extended abstract of 99.
 Available as
dvi,
ps,
pdf and
tex file.
 In: Proceedings Ninth Workshop on Quantitative Aspects of
Programming Languages, QAPL 2011, Saarbrücken, Germany,
April 2011 (M. Massink & G. Norman, eds.),
Electronic
Proceedings in Theoretical Computer Science 57, Open Publishing
Association, 2011, pp. 6173,
doi: 10.4204/EPTCS.57.5
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#87
In TCS 146, Bard Bloom presented rule formats for four main notions of
bisimulation with silent moves. He proved that weak bisimulation
equivalence is a congruence for any process algebra defined by WB cool
rules, and established similar results for rooted weak bisimulation
(Milner's "observational congruence"), branching bisimulation and
rooted branching bisimulation. This study reformulates Bloom's results
in a more accessible form and contributes analogues for (rooted)
ηbisimulation and (rooted) delay bisimulation. Moreover,
finite equational axiomatisations of rooted weak bisimulation
equivalence are provided that are sound and complete for finite
processes in any RWB cool process algebra. These require the
introduction of auxiliary operators with lookahead, and an extension
of Bloom's formats for this type of operator with lookahead. Finally,
a challenge is presented for which Bloom's formats fall short and
further improvement is called for.
Keywords: Concurrency, structural operational semantics, CCS, CSP,
compositionality, branching bisimulation, ηbisimulation,
delay bisimulation, weak bisimulation, complete axiomatizations.
Dedication: to Jan Bergstra,
on the occasion of his 60th birthday.
Note: An extended abstract of this paper appeared as
58.
 Available as
pdf,
ps,
dvi and
tex file.
 Theoretical Computer Science 412(28), pp. 32833302, 2011,
doi:
10.1016/j.tcs.2011.02.036
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#88
A wellknown problem in Petri net theory is to formalise an
appropriate causalitybased concept of process or run for
place/transition systems. The socalled individual token
interpretation, where tokens are distinguished according to their
causal history, giving rise to the processes of Goltz and Reisig, is
often considered too detailed. The problem of defining a fully
satisfying more abstract concept of process for general
place/transition systems has sofar not been solved. In this paper,
we recall the proposal of defining an abstract notion of process, here
called BDprocess, in terms of equivalence classes of
GoltzReisig processes, using an equivalence proposed by Best and
Devillers. It yields a fully satisfying solution for at least all
onesafe nets. However, for certain nets which intuitively have
different conflicting behaviours, it yields only one maximal abstract
process. Here we identify a class of place/transition systems, called
structural conflict nets, where conflict and concurrency
due to token multiplicity are clearly separated.
We show that, in the case of structural conflict nets, the equivalence
proposed by Best and Devillers yields a unique maximal abstract
process only for conflictfree nets.
Thereby BDprocesses constitute a simple and fully
satisfying solution in the class of structural conflict nets.
Highlights:
 We introduce the Petri net class of structural conflict nets (SCN).
 On SCNs, processes modulo Best/Devillers swapping give a satisfying semantics.
 This semantics adheres to the collective token interpretation and respects causality.
Note: This paper ends with an open question that is
answered in 90.
Keywords: Concurrency, Petri nets, PTsystems, causal semantics, processes.
We consider approaches for causal semantics of Petri nets, explicitly
representing dependencies between transition occurrences. For onesafe nets
or condition/eventsystems, the notion of process as defined by Carl Adam
Petri provides a notion of a run of a system where causal dependencies are
reflected in terms of a partial order. A wellknown problem is how to
generalise this notion for nets where places may carry several tokens.
Goltz and Reisig have defined such a generalisation by distinguishing tokens
according to their causal history. However, this socalled
individual token interpretation is often considered too detailed.
A number of approaches have tackled the problem of defining a more abstract
notion of process, thereby obtaining a socalled collective token
interpretation. Here we give a short overview on these attempts and then
identify a subclass of Petri nets, called structural conflict nets,
where the interplay between conflict and concurrency due to token multiplicity
does not occur. For this subclass, we define abstract processes as
equivalence classes of GoltzReisig processes. We justify this approach by
showing that we obtain exactly one maximal abstract process if and only if the
underlying net is conflictfree with respect to a canonical notion of conflict.
Keywords: Concurrency, Petri nets, PTsystems, causal semantics, processes.
Note: This paper continues and completes the work started in 89.
Together, these papers show that a structural conflict net is conflictfree if
and only if it has exactly one maximal run—equivalently formalised as maximal
BDrun, a maximal BDprocess or a maximal GRprocess up to swapping equivalence.
The "if" direction stems from 89, and "only if", together with
a taxonomy of suitable notions of maximality, is contributed here.
The main results of this paper appear again, with different proofs,
in 151 and 152.
 Informatik Bericht Nr. 201106, Institut für
Programmierung und Reaktive Systeme, TU Braunschweig, Germany 2011.
 Available as
pdf,
ps and
tex file.
 Archived at http://arxiv.org/abs/2103.00729.
 Extended abstract in: Proceedings 22th International Conference on Concurrency
Theory, CONCUR 2011, Aachen, Germany, September 2011
(J.P. Katoen & B. König, eds.), LNCS 6901, Springer, 2011, pp. 4359.
 Extended abstract available as
pdf and
ps.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#90
This paper describes work in progress towards an automated formal and
rigorous analysis of the Ad hoc OnDemand Distance Vector (AODV)
routing protocol, a popular protocol used in ad hoc wireless networks.
We give a brief overview of a model of AODV implemented in the UPPAAL
model checker, and describe experiments carried out to explore AODV's
behaviour in two network topologies. We were able to locate
automatically and confirm some known problematic and undesirable
behaviours. We believe this use of model checking as a diagnostic
tool complements other formal methods based protocol modelling and
verification techniques, such as process algebras. Model checking is
in particular useful for the discovery of protocol limitations and in
the development of improved variations.
Keywords: wireless mesh networks; mobile adhoc networks;
routing protocols; AODV; model checking, UPPAAL, process algebra, AWN.
We present a method for decomposing modal formulas for processes
with the internal action τ. To decide whether a process
algebra term satisfies a modal formula, one can check whether its
subterms satisfy formulas that are obtained by decomposing the
original formula. The decomposition uses the structural operational
semantics that underlies the process algebra. We use this
decomposition method to derive congruence formats for two weak and
rooted weak semantics: branching and ηbisimilarity.
Keywords: Concurrency, Structural Operational Semantics,
Compositionality, Congruence, Branching Bisimulation,
ηBisimulation, Modal Logic, Modal Decomposition.
Note: This paper properly contains the material of 64
and 62.
 Available as
dvi,
ps,
pdf and
tex file.
 Information and Computation 214, 2012, pp. 5985,
doi:10.1016/j.ic.2011.10.011
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#92
We propose a process algebra for wireless mesh networks that combines
novel treatments of local broadcast, conditional unicast and data
structures. In this framework, we model the Adhoc OnDemand Distance
Vector (AODV) routing protocol and (dis)prove crucial properties such
as loop freedom and packet delivery.
Keywords: wireless mesh networks; mobile adhoc networks;
process algebra; AWN; local broadcast; routing protocols; AODV; loop freedom.
Note: The material of this paper is included in 102.
 Available as
pdf,
ps and
tex file.
 In: Programming Languages and Systems, Proceedings 21st
European Symposium on Programming (ESOP'12); held as part of
the European Joint Conferences on Theory and Practice of
Software (ETAPS 2012), Tallinn, Estonia, March/April 2012
(Helmut Seidl, ed.), LNCS 7211, Springer, 2012, pp. 295315.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#93
This paper describes an automated, formal and rigorous analysis of the
Ad hoc OnDemand Distance Vector (AODV) routing protocol, a popular
protocol used in wireless mesh networks.
We give a brief overview of a model of AODV implemented in the UPPAAL
model checker. It is derived from a processalgebraic model which
reflects precisely the intention of AODV and accurately captures the
protocol specification. Furthermore, we describe experiments carried
out to explore AODV's behaviour in all network topologies up to 5 nodes.
We were able to automatically locate problematic and undesirable
behaviours. This is in particular useful to discover protocol
limitations and to develop improved variants. This use of model
checking as a diagnostic tool complements other formalmethodsbased
protocol modelling and verification techniques, such as process algebra.
Keywords: wireless mesh networks; mobile adhoc networks;
routing protocols; AODV; model checking, UPPAAL, process algebra, AWN.
Note: First steps towards this analysis appeared in 91.
 Available as
pdf.
 In: Proceedings 18th International Conference on
Tools and Algorithms for the Construction and Analysis of Systems (TACAS'12);
held as part of the European Joint Conferences on Theory and Practice of
Software (ETAPS 2012), Tallinn, Estonia, March/April 2012
(C. Flanagan & B. König, eds.), LNCS 7214, Springer, 2012, pp. 173187.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#94
We formalise a general concept of distributed systems as sequential
components interacting asynchronously. We define a corresponding
class of Petri nets, called LSGA nets, and precisely characterise
those system specifications which can be implemented as LSGA nets up
to branching STbisimilarity with explicit divergence.
Keywords: Concurrency, Petri nets, distributed systems,
reactive systems, asynchronous interaction, semantic equivalences.
Note: A further elaborated version of this paper appeared
as 101.

Technical Report 201110, Technical University of Braunschweig.
 Available as
ps,
pdf and
tex file.
 Archived at http://arxiv.org/abs/1207.3597.
 Extended abstract in: Proceedings 15th
International Conference on Foundations of Software Science
and Computation Structures (FoSSaCS 2012); held as part of
the European Joint Conferences on Theory and Practice of
Software (ETAPS 2012), Tallinn, Estonia, March/April 2012
(L. Birkedal, ed.), LNCS 7213, Springer, 2012, pp. 331345,
doi:10.1007/9783642287299_22.
 Extended abstract available as
ps,
pdf and
tex file.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#95
This triple issue of Formal Aspects of Computing constitutes a Festschrift
dedicated to Professor Charles Carroll Morgan, on the occasion of his sixtieth
birthday. The Festschrift consists of an invited paper and 23 scientific
research papers, all related to Carroll's own research interests.
Keywords: Carroll Morgan, Laws of Programming, Refinement Calculus,
Refinement of Ignorance, Herman's Ring, Security, Probability and Nondeterminism.
In this paper we present a rigorous analysis of the Ad hoc OnDemand
Distance Vector (AODV) routing protocol using a formal specification
in AWN (Algebra for Wireless Networks), a process algebra which has
been specifically tailored for the modelling of Mobile Ad Hoc Networks
and Wireless Mesh Network protocols. Our formalisation models the
exact details of the core functionality of AODV, such as route
discovery, route maintenance and error handling. We demonstrate how
AWN can be used to reason about critical protocol correctness
properties by providing a detailed proof of loop freedom. In contrast
to evaluations using simulation or other formal methods such as model
checking, our proof is generic and holds for any possible network
scenario in terms of network topology, node mobility, traffic pattern,
etc. A key contribution of this paper is the demonstration of how the
reasoning and proofs can relatively easily be adapted to protocol variants.
Keywords: wireless mesh networks; mobile adhoc networks;
routing protocols; AODV; process algebra, AWN.
Note: The material of this paper is included in 102.
 Available as
ps,
pdf and
source files.
 In: Proceedings 15th ACM International Conference on
Modeling, Analysis and Simulation of Wireless and Mobile Systems,
(MSWiM '12), Paphos, Cyprus, October 2012 (A.Y. Zomaya, B. Landfeldt & R. Prakash, eds),
ACM, 2012, pp. 203212, doi:10.1145/2387238.2387274.
 Free download from the ACM:
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#97
This paper proposes a definition of what it means for one system
description language to encode another one, thereby enabling an ordering
of system description languages with respect to expressive power.
I compare the proposed definition with other definitions of encoding and
expressiveness found in the literature, and illustrate it on a case study:
comparing the expressive power of CCS and CSP.
Keywords: Expressiveness, encodings, languages, translations,
compositionality, semantic equivalences, CCS, CSP.
 Available as
ps,
pdf and
source files.
 In: Proceedings Combined 19th International Workshop on Expressiveness in Concurrency
and 9th Workshop on Structured Operational Semantics (EXPRESS/SOS 2012),
Newcastle upon Tyne, UK, September 3, 2012 (B. Luttik & M.A. Reniers, eds.),
Electronic Proceedings in
Theoretical Computer Science 89, Open Publishing Association, pp. 8198,
doi:10.4204/EPTCS.89.7.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#98
We introduce a notion of realvalued reward testing for probabilistic
processes by extending the traditional nonnegativereward testing with
negative rewards. In this richer testing framework, the may and must
preorders turn out to be inverses. We show that for convergent
processes with finitely many states and transitions, but not in the
presence of divergence, the realreward musttesting preorder
coincides with the nonnegativereward musttesting preorder. To prove
this coincidence we characterise the usual resolutionbased testing in
terms of the weak transitions of processes, without having to involve
policies, adversaries, schedulers, resolutions, or similar structures
that are external to the process under investigation. This requires
establishing the continuity of our function for calculating testing
outcomes.
Keywords: Probabilistic processes, nondeterminism, transition systems,
testing equivalences, reward testing, failure simulation, divergence.
Note: An extended abstract of this paper appeared as
87.
 Available as
pdf,
ps and
tex file.
 Theoretical Computer Science 538, pp. 1636, 2014,
doi:
10.1016/j.tcs.2013.07.016
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#99
In the area of mobile adhoc networks and wireless mesh networks,
sequence numbers are often used in routing protocols to avoid routing
loops. It is commonly stated in protocol specifications that sequence
numbers are sufficient to guarantee loop freedom if they are
monotonically increased over time. A classical example for the use of
sequence numbers is the popular Ad hoc OnDemand Distance Vector
(AODV) routing protocol. The loop freedom of AODV is not only a
common belief, it has been claimed in the abstract of its RFC and at
least two proofs have been proposed. AODVbased protocols such as
AODVv2 (DYMO) and HWMP also claim loop freedom due to the same use of
sequence numbers.
In this paper we show that AODV is not a priori loop free; by this we
counter the proposed proofs in the literature. In fact, loop freedom
hinges on nonevident assumptions to be made when resolving
ambiguities occurring in the RFC. Thus, monotonically increasing
sequence numbers, by themselves, do not guarantee loop freedom.
Keywords: wireless mesh networks; mobile adhoc networks; loop freedom;
routing protocols; AODV; process algebra.
Note: The material of this paper is included in 102,
although the presentation of the material is somewhat different.
 Available as
pdf,
ps and
tex file.
 In: Proceedings 16th ACM International Conference on
Modeling, Analysis and Simulation of Wireless and Mobile Systems
(MSWiM '13), Barcelona, Spain, November 2013, pp. 91100, ACM, 2013,
doi:10.1145/2507924.2507943.
 Free download from the ACM:
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#100
We formalise a general concept of distributed systems as sequential
components interacting asynchronously. We define a corresponding
class of Petri nets, called LSGA nets, and precisely characterise
those system specifications which can be implemented as LSGA nets up
to branching STbisimilarity with explicit divergence.
Keywords: Concurrency, Petri nets, distributed systems,
reactive systems, asynchronous interaction, semantic equivalences.
Note: This paper is adapted from 95; it
characterises distributability for a slightly larger range of semantic
equivalence relations, and incorporates various remarks stemming from
78.
Route finding and maintenance are critical for the performance of networked systems, particularly
when mobility can lead to highly dynamic and unpredictable environments; such operating contexts
are typical in wireless mesh networks. Hence correctness and good performance are strong requirements
of routing protocols.
In this paper we propose AWN (Algebra for Wireless Networks), a process algebra tailored to
the modelling of Mobile Ad hoc Network (MANET) and Wireless Mesh Network (WMN) protocols.
It combines novel treatments of local broadcast, conditional unicast and data structures.
In this framework, we present a rigorous analysis of the Ad hoc OnDemand Distance Vector
(AODV) protocol, a popular routing protocol designed for MANETs and WMNs, and one of the four
protocols currently defined as an RFC (request for comments) by the IETF MANET working group.
We give a complete and unambiguous specification of this protocol, thereby formalising the RFC
of AODV, the de facto standard specification, given in English prose. In doing so, we had to make
nonevident assumptions to resolve ambiguities occurring in that specification. Our formalisation
models the exact details of the core functionality of AODV, such as route maintenance and error
handling, and only omits timing aspects.
The process algebra allows us to formalise and (dis)prove crucial properties of mesh network
routing protocols such as loop freedom and packet delivery. We are the first to provide a detailed
proof of loop freedom of AODV. In contrast to evaluations using simulation or other formal methods
such as model checking, our proof is generic and holds for any possible network scenario in terms of
network topology, node mobility, traffic pattern, etc. Due to ambiguities and contradictions the RFC
specification allows several readings. For this reason, we analyse multiple interpretations. In fact we
show for more than 5000 interpretations whether they are loop free or not. Thereby we demonstrate
how the reasoning and proofs can relatively easily be adapted to protocol variants.
Using our formal and unambiguous specification, we find some shortcomings of AODV that can
easily affect performance. Examples are nonoptimal routes established by AODV and the fact that
some routes are not found at all. These problems are analysed and improvements are suggested.
As the improvements are formalised in the same process algebra, carrying over the proofs is again
relatively easy.
Keywords: wireless mesh networks; mobile adhoc networks;
process algebra; AWN; local broadcast; routing protocols; AODV; loop freedom.
Note: This paper includes the material of
[93, 97, 100, 114],
although the presentation of the material is somewhat different.
The loop freedom proof described herein has been
mechanised in the theorem prover Isabelle/HOL in [103, 104].
This paper presents the mechanization of a process algebra for Mobile Ad hoc
Networks and Wireless Mesh Networks, and the development of a compositional
framework for proving invariant properties.
Mechanizing the core process algebra in Isabelle/HOL is relatively standard,
but its layered structure necessitates special treatment.
The control states of reactive processes, such as nodes in a network, are
modelled by terms of the process algebra.
We propose a technique based on these terms to streamline proofs of
inductive invariance.
This is not sufficient, however, to state and prove invariants that relate
states across multiple processes (entire networks).
To this end, we propose a novel compositional technique for lifting global
invariants stated at the level of individual nodes to networks of nodes.
Keywords: wireless mesh networks; mobile adhoc networks;
process algebra; AWN; interactive theorem proving; Isabelle/HOL; invariants;
compositional lifting technique
Note: This is an extended abstract of 112.
 Available as
dvi,
pdf and
ps.
 The Isabelle/HOL source files, and a full proof document, are available in the Archive of Formal Proofs, at
http://afp.sourceforge.net/entries/AWN.shtml.
 Archived at http://arxiv.org/abs/1407.3519.
 In: Proceedings 5th International Conference on Interactive Theorem Proving,
ITP 2014; held as Part of the Vienna Summer of Logic, VSL 2014,
Vienna, Austria, July 2014 (G. Klein & R. Gamboa, eds.),
LNCS 8558, Springer, 2014, pp. 144159,
doi: 10.1007/9783319089706_10
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#103
The Ad hoc Ondemand Distance Vector (AODV) routing protocol allows the
nodes in a Mobile Ad hoc Network (MANET) or a Wireless Mesh Network (WMN) to
know where to forward data packets. Such a protocol is 'loop free' if it
never leads to routing decisions that forward packets in circles. This paper
describes the mechanization of an existing penandpaper proof of loop
freedom of AODV in the interactive theorem prover Isabelle/HOL. The
mechanization relies on a novel compositional approach for lifting
invariants to networks of nodes. We exploit the mechanization to analyse
several improvements of AODV and show that Isabelle/HOL can reestablish
most proof obligations automatically and identify exactly the steps that are
no longer valid.
Keywords: wireless mesh networks; mobile adhoc networks;
routing protocols; AODV; loop freedom; process algebra; AWN;
interactive theorem proving; Isabelle/HOL; invariants;
compositional lifting technique
 Available as
pdf.
 The Isabelle/HOL source files, and a full proof document, are available in the Archive of Formal Proofs, at
http://afp.sourceforge.net/entries/AODV.shtml.
 Archived at http://arxiv.org/abs/1505.05646.
 In: Proceedings 12th International Symposium on Automated Technology
for Verification and Analysis, ATVA 2014, Sydney, Australia, November 2014
(F. Cassez and J.F. Raskin, eds.), LNCS 8837, Springer, 2014, pp. 4763,
doi: 10.1007/9783319119366_5
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#104
In March 1988, we organised a workshop on âCombining Compositionality and Concurrencyâ
in KĂ¶nigswinter near Bonn, Germany. We were motivated by the following dichotomy.
One the one hand, a theory of concurrency was initiated by Carl Adam Petri, with notions
like causality, conflict, and concurrency. One the other hand, a theory of communicating
processes was developed by Robin Milner and Tony Hoare, where the emphasis was put on
composing processes by algebraic operators like sequential, nondeterministic, and parallel
composition.
For quite a some time little interaction took place between the followers of these two
lines of research. Then it was more and more realized that a full understanding, analysis or
construction of parallel processes is impossible without combining the best from concurrency
and compositionality. The idea of the workshop was therefore to invite researchers active in
the area of combining compositionality and concurrency.
In the meantime the relationships between these two directions have been carefully investigated.
Today, the elements of the different semantic approaches are freely mixed. Also,
the scope of systems that are modelled by concurrent or process algebraic means is much
extended, for example, to mobile and probabilistic systems.
In 2013, we called for a workshop â25 Years of Combining Compositionality and Concurrencyâ.
We received very enthusiastic responses, and the jubilee workshop took place in
August 2013 at the very same venue in KĂ¶nigswinter as the first one.1 This special issue
results from a call for papers sent out right after the workshop. It comes in
two parts: this first part comprises three papers.
The paper Revisiting Causality, Coalgebraically by Roberto Bruni, Ugo Montanari, and
Matteo Sammartino recasts a causal semantics of concurrency originally defined by Darondeau
and Degano in a coalgebraic setting. By exploiting the equivalence between coalgebras
over a class of presheaves and history dependent automata, they derive a compact model.
The paper Synthesis and Reengineering of Persistent Systems by Eike Best and Raymond
Devillers considers synthesis and reengineering problems in the framework of finitestate
labelled transitions systems and place/transition Petri nets. They obtain exact conditions for
a finite persistent transition system to be isomorphically implementable by a bounded Petri
net exhibiting persistence in a structural way. Moreover, they derive an efficient algorithm to
find such a net if it exists.
The paper Revisiting Bisimilarity and its Modal Logic for Nondeterministic and Probabilistic
Processes by Marco Bernado, Rocco De Nicola, and Michele Loretti investigates
new notions of bisimilarity that correspond to extensions of the logic PML to probabilistic
processes with internal nondeterminism; PML itself is a probabilistic version of HennessyâMilner
logic introduced by Larsen and Skou to characterise bisimilarity over probabilistic
processes without internal nondeterminism.
Keywords:
concurrency, compositionality, causality, coalgebras, synthesis, Petri nets, bisimilarity,
probabilistic processes.
 Acta Informatica 52(1), 2015, pp. 34,
doi: 10.1007/s002360140213y
 Available as
pdf.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#105
To prove liveness properties of concurrent systems, it is often
necessary to postulate progress, fairness and justness properties.
This paper investigates how the necessary progress, fairness and
justness assumptions can be added to or incorporated in a standard
processalgebraic specification formalism. We propose a formalisation
that can be applied to a wide range of process algebras. The
presented formalism is used to reason about route discovery and packet
delivery in the setting of wireless networks.
Keywords:
progress; justness; fairness; liveness; process algebra;
labelled transition systems; Lineartime Temporal Logic;
CCS, broadcast communication; fairness specifications.
In the process algebra community it is sometimes suggested that,
on some level of abstraction, any distributed system can be
modelled in standard processalgebraic specification formalisms like CCS.
This sentiment is strengthened by results testifying that CCS,
like many similar formalisms, is Turing powerful and provides a
mechanism for interaction.
This paper counters that sentiment by presenting a simple fair
scheduler—one that in suitable variations occurs in many
distributed systems—of which no implementation can be
expressed in CCS, unless CCS is enriched with a fairness assumption.
Since Dekker's and Peterson's mutual exclusion protocols implement
fair schedulers, it follows that these protocols cannot be rendered
correctly in CCS without imposing a fairness assumption. Peterson
expressed this algorithm correctly in pseudocode without resorting to
a fairness assumption, so it furthermore follows that CCS lacks the
expressive power to accurately capture such pseudocode.
Keywords:
process algebra; CCS; expressiveness, fair schedulers,
progress; justness; fairness; Petri nets;
labelled transition systems; Lineartime Temporal Logic;
mutual exclusion protocols.
Dedication:
It is our great pleasure to dedicate this paper to Walter Vogler on
the occasion of his 60th birthday.
We have combined two of Walter's main interests: Petri nets and
process algebra.
In fact, we proved a result about Petri nets that had been proven
before by Walter, but in a restricted form,
as we discovered only after finishing our proof.
We also transfer this result to the process algebra CCS.
Beyond foundational research in the theory of concurrent systems,
Walter achieved excellent results in related subjects such
as temporal logic and efficiency.
In addition to being a dedicated researcher, he is also
meticulous in all of his endeavours, including his writing.
As a consequence his scientific papers tend to contain no flaws,
which is just one of the reasons that makes reading them so enjoyable.
It's fair to say: ``CCS Walter!'' –Congratulations and Continuous Success!
This is the second part of the special issue motivated by the workshop "25 Years of Combining
Compositionality and Concurrency" that we organised in August 2013 in KĂ¶nigswinter near
Bonn, Germany. The first part was published in Acta Informatica (2015) 52(1):3106. For
an introduction to the topic see our editorial there. This second part comprises four papers.
The paper Richer Interface Automata with Optimistic and Pessimistic Compatibility by
Gerald LĂŒttgen, Walter Vogler, and Sascha Fendrich addresses componentbased reasoning
for concurrent systems via modal interface automata (MIA). The authors study optimistic
and pessimistic MIA variants with internal musttransitions. They define conjunction and
disjunction on interfaces as well as mechanisms for extending alphabets.
The paper Compositional Verification of Asynchronous Concurrent Systems using CADP
by Hubert Garavel, FrĂ©dĂ©ric Lang, and Radu Mateescu investigates how various compositional
techniques help to fight the statespace explosion in the verification of asynchronous
messagepassing systems. The techniques are implemented in the toolbox CADP (Construction
and Analysis of Distributed Processes). The authors compare the different approaches
using a common case study.
The paper Denotational FixedPoint Semantics for Constructive Scheduling of Synchronous
Concurrency by JoaquĂn Aguado, Michael Mendler, Reinhard von Hanxleden, and Insa
Fuhrmann defines an abstract semantic domain and an associated denotational semantics
for synchronous programs. The semantics induces three notions of constructiveness, among
them the new notion of Input Berryconstructiveness (IBC) for these programs. The authors
study behavioural properties of IBC programs.
The paper Compositional Construction of Most General Controllers by Joachim Klein,
Christel Baier, and Sascha KlĂŒppelholz considers for given transitions systems conjunctions
of lineartime objectives to be achieved by a controller. The authors present gamebased
algorithms for the compositional construction of most general controllers for invariance,
reachability, and ωregular objectives.
Keywords:
concurrency, compositionality, modal interface automata, asynchronous systems, CADP,
denotational semantics, synchronous programs, most general controllers.
 Acta Informatica 52(45), 2015, pp. 303304,
doi: 10.1007/s0023601502403
 Available as
pdf.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#108
A general method is established to derive a groundcomplete axiomatization for a weak semantics from
such an axiomatization for its concrete counterpart, in the context of the process algebra BCCS.
This transformation moreover preserves omegacompleteness.
It is applicable to semantics at least as coarse as impossible futures semantics.
As an application, ground and omegacomplete axiomatizations are derived for weak failures,
completed trace and trace semantics. We then present a finite, sound, groundcomplete axiomatization
for the concrete impossible futures preorder,
which implies a finite, sound, groundcomplete axiomatization for
the weak impossible futures preorder. In contrast,
we prove that no finite, sound axiomatization for BCCS modulo concrete and weak
impossible futures equivalence is groundcomplete.
If the alphabet of actions is infinite, then the aforementioned groundcomplete
axiomatizations are shown to be omegacomplete. If the
alphabet is finite, we prove that the inequational theories of BCCS
modulo the concrete and weak impossible futures preorder lack such a finite basis.
Keywords: Concurrency, Process Algebra, BCCS, Equational Logic, labeled transition systems,
complete axiomatizations, failures semantics, impossible futures semantics.
Note: The results on complete axiomatizations, and their
absence, for weak failures and weak impossible futures
semantics occurred before in 81, but
without the proof strategy of distilling axiomatizations for weak
semantics from those of concrete semantics.
Encodings or the proof of their absence are the main way to
compare process calculi. To analyse the quality of encodings and to
rule out trivial or meaningless encodings, they are augmented with
quality criteria. There exists a bunch of different criteria and
different variants of criteria in order to reason in different
settings. This leads to incomparable results. Moreover it is not
always clear whether the criteria used to obtain a result in a
particular setting do indeed fit to this setting. We show how to
formally reason about and compare encodability criteria by mapping
them on requirements on a relation between source and target terms
that is induced by the encoding function. In particular we analyse the
common criteria full abstraction, operational correspondence,
divergence reflection, success sensitiveness, and respect of barbs;
e.g. we analyse the exact nature of the simulation relation (coupled
simulation versus bisimulation) that is induced by different variants
of operational correspondence. This way we reduce the problem of
analysing or comparing encodability criteria to the better understood
problem of comparing relations on processes.
Keywords: Process Algebra, expressiveness, encodings, reduction semantics, barbs,
operational correspondence, semantic equivalences, bisimulation, coupled simulation.
Note: All claims in this paper have been proved using the
interactive theorem prover Isabelle/HOL. The Isabelle implementation
of the theories is available in the Archive of Formal Proofs,
at
http://afp.sourceforge.net/entries/Encodability_Process_Calculi.shtml
 In: Proceedings Combined 22th International Workshop on Expressiveness in Concurrency
and 12th Workshop on Structured Operational Semantics (EXPRESS/SOS 2015),
Madrid, Spain, 31st August 2015 (S. Crafa and D.E. Gebler, eds.),
Electronic
Proceedings in Theoretical Computer Science 190, Open Publishing
Association, pp. 4660.
doi:10.4204/EPTCS.190.4.
 Available as
pdf and
source files.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#110
 The Isabelle/HOL source files, and a full proof document,
are available in the Archive of Formal Proofs,
at
http://afp.sourceforge.net/entries/Encodability_Process_Calculi.shtml
In 1987 ErnstRüdiger Olderog provided an operational Petri net
semantics for a subset of CCSP, the union of Milner's CCS and Hoare's
CSP. It assigns to each process term in the subset a labelled, safe
place/transition net. To demonstrate the correctness of the approach,
Olderog established agreement (1) with the standard interleaving
semantics of CCSP up to strong bisimulation equivalence, and (2) with
standard denotational interpretations of CCSP operators in terms of
Petri nets up to a suitable semantic equivalence that fully respects
the causal structure of nets. For the latter he employed a lineartime
semantic equivalence, namely having the same causal nets. This paper
strengthens (2), employing a novel branchingtime version of this
semantics–structure preserving bisimilarity–that moreover
preserves inevitability. I establish that it is a congruence for the
operators of CCSP.
Keywords: Concurrency, Petri nets, process algebra, CCSP,
operational semantics, semantic equivalences, linear time,
branching time, bisimulation, interleaving vs. partial orders,
inevitability, action refinement, realtime consistency,
causality, causal nets, progress, justness.
Dedication: to ErnstRüdiger Olderog,
on the occasion of his 60th birthday.
 In: Proceedings Correct System Design  Symposium in Honor of
ErnstRüdiger Olderog on the Occasion of His 60th Birthday
(R. Meyer, A. Platzer & H. Wehrheim, eds.),
Oldenburg, Germany, September 89, 2015, LNCS 9360,
Springer, pp. 99â130,
doi:10.1007/9783319235066_9.
 Available as
pdf,
postscript and
source files.
 Archived at http://arxiv.org/abs/1509.05842.
 Slides.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#111
This paper presents the mechanization of a process algebra for Mobile
Ad hoc Networks and Wireless Mesh Networks, and the development of a
compositional framework for proving invariant properties. Mechanizing
the core process algebra in Isabelle/HOL is relatively standard, but
its layered structure necessitates special treatment. The control
states of reactive processes, such as nodes in a network, are modelled
by terms of the process algebra. We propose a technique based on these
terms to streamline proofs of inductive invariance. This is not
sufficient, however, to state and prove invariants that relate states
across multiple processes (entire networks). To this end, we propose a
novel compositional technique for lifting global invariants stated at
the level of individual nodes to networks of nodes.
Keywords: interactive theorem proving; Isabelle/HOL; process algebra;
AWN; wireless mesh networks; mobile adhoc networks; compositional invariant proofs
Note: An extended abstract of this paper appeared as
103.
This volume contains the proceedings of MARS 2015, the first workshop
on Models for Formal Analysis of Real Systems, held on November
23, 2015 in Suva, Fiji, as an affiliated workshop of LPAR 2015,
the 20th International Conference on Logic for Programming,
Artificial Intelligence and Reasoning.
The workshop emphasises modelling over verification.
It aims at discussing the lessons learned from making formal methods
for the verification and analysis of realistic systems. Examples are:
(1) Which formalism is chosen, and why?
(2) Which abstractions have to be made and why?
(3) How are important characteristics of the system modelled?
(4) Were there any complications while modelling the system?
(5) Which measures were taken to guarantee the accuracy of the model?
We invited papers that present full models of real systems, which may
lay the basis for future comparison and analysis. An aim of the
workshop is to present different modelling approaches and discuss pros
and cons for each of them. Alternative formal descriptions of the
systems presented at this workshop are encouraged, which should foster
the development of improved specification formalisms.
This paper presents a formal specification of the Ad hoc OnDemand
Distance Vector (AODV) routing protocol using AWN (Algebra for
Wireless Networks), a recent process algebra which has been
tailored for the modelling of Mobile Ad Hoc Networks and Wireless Mesh Network
protocols. Our formalisation models the exact details of the core
functionality of AODV, such as route discovery, route maintenance and
error handling. We demonstrate how AWN can be used to reason about
critical protocol properties by providing detailed proofs of loop
freedom and route correctness.
Keywords: Wireless mesh networks; mobile adhoc networks;
routing protocols; AODV; process algebra; AWN; loop freedom.
Note: Most of the material of this paper is included in 102,
although the presentation is somewhat different.
This paper proposes a timed process algebra for wireless networks,
an extension of the Algebra for Wireless Networks. It combines
treatments of local broadcast, conditional unicast and data structures,
which are essential features for the modelling of network protocols.
In this framework we model and analyse the Ad hoc OnDemand Distance
Vector routing protocol, and show that, contrary to claims in the
literature, it fails to be loop free. We also present boundary
conditions for a fix ensuring that the resulting protocol is indeed loop free.
Keywords: Wireless mesh networks; mobile adhoc networks;
timed process algebra; AWN; routing protocols; AODV; loop freedom.
 Technical Report 9145, NICTA.
 Available as
pdf,
ps and
dvi.
 Archived at http://arxiv.org/abs/1606.03663.
 Extended abstract in: P. Thiemann, ed.:
Programming Languages and Systems, Proceedings 25th
European Symposium on Programming (ESOP 2016); held as part of
the European Joint Conferences on Theory and Practice of
Software (ETAPS 2016), Eindhoven, The Netherlands, April 2016,
LNCS 9632, Springer, pp. 95122,
doi:10.1007/9783662494981_5
 Extended abstract available as
pdf,
ps,
dvi and
tex source.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#115
Often fairness assumptions need to be made in order to establish
liveness properties of distributed systems, but in many situations
these lead to false conclusions.
This document presents a research agenda aiming at laying the
foundations of a theory of concurrency that is equipped to ensure
liveness properties of distributed systems without making fairness
assumptions. This theory will encompass process algebra, temporal
logic and semantic models, as well as treatments of realtime. The
agenda also includes developing a methodology that allows successful
application of this theory to the specification, analysis and
verification of realistic distributed systems, including routing
protocols for wireless networks.
Contemporary process algebras and temporal logics fail to make
distinctions between systems of which one has a crucial liveness
property and the other does not, at least when assuming justness,
a strong progress property, but not assuming fairness.
Setting up an alternative framework involves giving up on identifying
strongly bisimilar systems, inventing new induction principles,
developing new axiomatic bases for process algebras and new congruence
formats for operational semantics, and creating new treatments of time
and probability.
Even simple systems like fair schedulers or mutual exclusion protocols
cannot be accurately specified in standard process algebras (or Petri
nets) in the absence of fairness assumptions. Hence the work involves
the study of adequate language or model extensions, and their
expressive power.
Keywords: Liveness, fairness, justness, progress, distributed systems,
concurrency, process algebra, temporal logic, labelled transition systems,
Petri nets, semantic equivalences, strong bisimulation, fair schedulers,
mutual exclusion, expressiveness, routing protocols, wireless mesh networks,
structural operational semantics, probabilistic processes, realtime,
approximation induction principle, recursive specification principle.
Note: Most of the material of this paper is included in 138,
although the presentation is somewhat different.
Earlier we presented a method to decompose modal formulas for processes with
the internal action τ; congruence formats for branching and
ηbisimilarity were derived on the basis of this decomposition method.
The idea is that a congruence format for a semantics must ensure that
formulas in the modal characterisation of this semantics are always decomposed
into formulas in this modal characterisation. Here the decomposition method is
enhanced to deal with modal characterisations that contain a modality
<τ*a>φ, to derive congruence formats for delay and weak bisimilarity.
Keywords: Structural operational semantics, congruence formats,
weak bisimilarity, modal characterisation.
Note: This is an extended abstract of 117.
 Available as
pdf and
tex source.
 In: Proceedings 31st Annual ACM/IEEE Symposium on Logic in
Computer Science, LICS 2016, New York City, USA, July 2016,
ACM, 2016, pp. 778787,
doi:10.1145/2933575.2933590
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#116
Earlier we presented a method to decompose modal formulas for processes with
the internal action τ, and congruence formats for branching and
ηbisimilarity were derived on the basis of this decomposition method.
The idea is that a congruence format for a semantics must ensure that the
formulas in the modal characterisation of this semantics are always decomposed
into formulas that are again in this modal characterisation. In this followup
paper the decomposition method is enhanced to deal with modal characterisations
that contain a modality <τ*a>φ, to derive congruence formats for
delay and weak bisimilarity.
Keywords: Structural operational semantics, congruence formats,
weak bisimilarity, modal characterisation.
Note: An extended abstract of this paper appeared as
116.
Erratum: With Definition 20.4b(i) as formulated originally, Proposition 5 does not hold.
A corrected Definition 20.4b appears in the revision below.
We show that the proof nets introduced in [50, 57]
for MALL (Multiplicative Additive Linear Logic, without units) identify
cutfree proofs modulo rule commutation: two cutfree proofs
translate to the same proof net if and only if one can be obtained
from the other by a succession of rule commutations.
This result holds with and without the mix rule, and we extend it with cut.
Keywords: Linear logic, proof nets, additives, rule commutations.
I review the three principal methods to assign meaning to recursion in
process algebra: the denotational, the operational and the algebraic
approach, and I extend the latter to unguarded recursion.
Keywords: Process algebra, unguarded recursion, denotational semantics,
operational semantics, algebraic semantics.
Dedication:
Jan Bergstra has put his mark on theoretical computer science by a consistent stream of original
ideas, controversial opinions, and novel approaches. He sometimes reorganised the arena, enabling
others to follow. I, for one, might never have entered computer science if it wasn't for Jan's
support and encouragement, and will never forget the team spirit in the early days of process
algebra in his group at CWI. This paper is dedicated to Jan, at the occasion of his 65^{th}
birthday and retirement.
 Available as
dvi,
ps,
pdf and
tex source.
 In: Liber Amicorum for Jan A. Bergstra (I. Bethke and B. Bredeweg
and A. Ponse, eds.), Informatics Institute, University of Amsterdam,
2016, pp. 5859.
 Archived at http://arxiv.org/abs/1702.07838.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#119
I present a branching time model of CSP that is finer than all other models of CSP proposed thus far.
It is obtained by taking a semantic equivalence from the linear time – branching time
spectrum, namely divergencepreserving coupled similarity, and showing that it is a
congruence for the operators of CSP. This equivalence belongs to the bisimulation family
of semantic equivalences, in the sense that on transition systems without internal
actions it coincides with strong bisimilarity. Nevertheless, enough of the equational
laws of CSP remain to obtain a complete axiomatisation for closed, recursionfree terms.
Keywords: Process algebra, CSP, branching time, coupled similarity, complete axiomatisation.
Dedication:
to Bill Roscoe, on the occasion of his 60th birthday.
 Available as
dvi,
ps,
pdf and
tex source.
 In: Concurrency, Security, and Puzzles — Essays Dedicated to Andrew William Roscoe on the
Occasion of His 60th Birthday (Th. GibsonRobinson and Ph.J. Hopcroft and R. Lazic, eds.),
LNCS 10160, Springer, 2017, pp. 272293,
doi:10.1007/9783319510460_14.
 Archived at http://arxiv.org/abs/1702.07844.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#120
We present a formal model for a fragmentation and a reassembly protocol
running on top of the standardised CAN bus, which is widely used in
automotive and aerospace applications. Although the CAN bus
comes with an inbuilt mechanism for prioritisation, we argue that this is
not sufficient and provide another protocol to overcome this shortcoming.
Keywords: CAN bus, fragmentation protocol, priority inversion, process algebra, AWN.
Bloom, Fokkink & van Glabbeek (2004) presented a
method to decompose formulas from HennessyMilner logic with regard to
a structural operational semantics specification. A term in the
corresponding process algebra satisfies a HennessyMilner formula if
and only if its subterms satisfy certain formulas, obtained by
decomposing the original formula. They used this decomposition method
to derive congruence formats in the realm of structural operational
semantics. In this paper it is shown how this framework can be
extended to specifications that include bounded lookahead in their
premises. This extension is used in the derivation of a congruence
format for the partial trace preorder.
Keywords: Structural operational semantics, compositionality,
congruence formats, modal characterisation, lookahead.
 Available as
pdf and
tex source.
 In: Proceedings 26th EACSL Annual Conference on Computer Science Logic,
CSL 2017, Stockholm, Sweden, August 2017 (V. Goranko & M. Dam, eds.)
Leibniz International Proceedings in Informatics (LIPIcs) 82, Schloss
Dagstuhl–LeibnizZentrum für Informatik, 2017, pp. 25:125:20,
doi:10.4230/LIPIcs.CSL.2017.25.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#122
In this paper I distinguish two (pre)congruence requirements for semantic
equivalences and preorders on processes given as closed terms in a system
description language with a recursion construct. A lean congruence
preserves equivalence when replacing closed subexpressions of a process by
equivalent alternatives. A full congruence moreover allows replacement
within a recursive specification of subexpressions that may contain recursion
variables bound outside of these subexpressions.
I establish that bisimilarity is a lean (pre)congruence for recursion for all
languages with a structural operational semantics in the ntyft/ntyxt format.
Additionally, it is a full congruence for the tyft/tyxt format.
Keywords: Structural Operational Semantics, Congruence formats,
Recursion, Bisimulation.
 Available as
dvi,
ps,
pdf and
tex source.
 Archived at http://arxiv.org/abs/1704.03160.
 (Draft, released August 2016, available as
dvi,
ps,
pdf and
tex source.)
 In: Proceedings 32nd Annual ACM/IEEE Symposium on Logic in
Computer Science, LICS 2017, Reykjavik, Iceland, June 2017, IEEE
Computer Society Press, Los Alamitos 2017,
doi:10.1109/LICS.2017.8005142.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#123
In two earlier papers we derived congruence formats for weak semantics
on the basis of a decomposition method for modal formulas. The idea is
that a congruence format for a semantics must ensure that the formulas
in the modal characterisation of this semantics are always decomposed
into formulas that are again in this modal characterisation. Here this
work is extended with important stability and divergence requirements.
Stability refers to the absence of a tautransition. We show, using the
decomposition method, how congruence formats can be relaxed for weak
semantics that are stabilityrespecting. Divergence, which refers to the
presence of an infinite sequence of tautransitions, escapes the
inductive decomposition method. We circumvent this problem by proving
that a congruence format for a stabilityrespecting weak semantics is
also a congruence format for its divergencepreserving counterpart.
Keywords: Structural operational semantics, compositionality,
congruence formats, modal characterisation, divergence,
weak semantics, branching bisimulation
Note: This is an extended abstract of 125.
 Available as
pdf and
tex source.
 In: Proceedings 28th International Conference on Concurrency
Theory, CONCUR 2017, Berlin, Germany, September 2017
(R. Meyer & U. Nestmann, eds.), Leibniz International
Proceedings in Informatics (LIPIcs) 85, Schloss
Dagstuhl–LeibnizZentrum für Informatik, 2017, pp. 15:115:16,
doi:10.4230/LIPIcs.CONCUR.2017.15.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#124
In two earlier papers we derived congruence formats with regard to
transition system specifications for weak semantics on the basis of a
decomposition method for modal formulas. The idea is that a congruence
format for a semantics must ensure that the formulas in the modal
characterisation of this semantics are always decomposed into formulas
that are again in this modal characterisation. The stability and
divergence requirements that are imposed on many of the known weak
semantics have so far been outside the realm of this method. Stability
refers to the absence of a tautransition. We show, using the
decomposition method, how congruence formats can be relaxed for weak
semantics that are stabilityrespecting. This relaxation for instance
brings the priority operator within the range of the stabilityrespecting
branching bisimulation format. Divergence, which refers to the presence
of an infinite sequence of tautransitions, escapes the inductive
decomposition method. We circumvent this problem by proving that a
congruence format for a stabilityrespecting weak semantics is also a
congruence format for its divergencepreserving counterpart.
Keywords: Structural operational semantics, compositionality,
congruence formats, modal characterisation, divergence,
weak semantics, branching bisimulation
Note: An extended abstract of this paper appeared as 124.
In contrast to common belief, the Calculus of Communicating Systems (CCS) and
similar process algebras lack the expressive power to accurately capture mutual
exclusion protocols without enriching the language with fairness assumptions.
Adding a fairness assumption to implement a mutual exclusion protocol seems
counterintuitive. We employ a signalling operator, which can be combined with
CCS, or other process calculi, and show that this minimal extension is
expressive enough to model mutual exclusion: we confirm the correctness of
Peterson's mutual exclusion algorithm for two processes, as well as Lamport's
bakery algorithm, under reasonable assumptions on the underlying memory model.
The correctness of Peterson's algorithm for more than two processes requires
stronger, less realistic assumptions on the underlying memory model.
Keywords: mutual exclusion protocols, liveness, process algebra, CCS,
signals, nonblocking reading, progress, justness, fairness,
expressiveness, structural operational semantics, memory models.
We prove that rooted divergencepreserving branching bisimilarity is
a congruence for the process specification language consisting of
0, action prefix, choice, and the recursion construct μX._.
Keywords: Process algebra; Recursion; Branching bisimulation; Divergence;
Congruence.
Process calculi may be compared in their expressive power by means of encodings
between them. A widely accepted definition of what constitutes a valid
encoding for (dis)proving relative expressiveness results between process
calculi was proposed by Gorla. Prior to this work, diverse encodability
and separation results were generally obtained using distinct, and often
incompatible, quality criteria on encodings.
Textbook examples of valid encoding are the encodings proposed by Boudol
and by Honda & Tokoro of the synchronous choicefree πcalculus into
its asynchronous fragment, illustrating that the latter is no less
expressive than the former. Here I formally establish that these
encodings indeed satisfy Gorla's criteria.
Keywords: Process calculi, expressiveness, quality
criteria for encodings, valid encoding, πcalculus
Two process calculi may be compared in their expressive power using encodings between them.
Not every such translation is meaningful and therefore quality criteria are necessary.
There are several frameworks to assess the quality of encodings.
A rather prominent approach consists of five criteria for valid encodings collected by Gorla.
An alternative notion of validity up to a semantic equivalence was proposed by one of the authors.
Here the quality of the encoding is measured by the strength of the semantic equivalence that makes it valid.
In this paper we analyse two wellknown translations from the synchronous into the asynchronous
πcalculus, both meeting Gorla's criteria,
and evaluate the encodings' validity up to different semantic equivalences.
While Honda and Tokoro's translation is valid only for the weakest of
the considered behavioural equivalences, Boudol's encoding also respects stronger ones.
One could hence argue that Boudol's translation is more faithful.
Keywords: Process calculi, expressiveness, quality criteria for encodings, πcalculus
Note: The material of the paper has been incorporated in 141.
 Available as
pdf and
tex file.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#129
This paper proposes a definition of what it means for one system
description language to encode another one, thereby enabling an ordering
of system description languages with respect to expressive power.
I compare the proposed definition with other definitions of encoding and
expressiveness found in the literature, and illustrate it on a
wellknown case study: the encoding of the synchronous in
the asynchronous πcalculus.
Keywords: Expressiveness, encodings, languages, translations,
compositionality, semantic equivalences, πcalculus.
 May'18: Available as
dvi,
ps,
pdf and
tex source.
 Archived at http://arxiv.org/abs/1805.10415.
 Extended abstract in: Proceedings 21st
International Conference on Foundations of Software Science
and Computation Structures (FoSSaCS 2018); held as part of
the European Joint Conferences on Theory and Practice of
Software (ETAPS 2018), Thessaloniki, Greece, April 2018
(C. Baier & U. Dal Lago, eds.), LNCS 10803,
Springer, 2018, pp. 183202, doi:10.1007/9783319893662_10.
 February'18: Extended abstract available as
dvi,
ps,
pdf and
tex source.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#130
This volume contains the joint proceedings of MARS 2018, the third
workshop on Models for Formal Analysis of Real Systems, and VPT 2018,
the sixth international workshop on Verification and Program
Transformation, held together on April 20, 2018 in Thessaloniki,
Greece, as part of ETAPS 2018, the European Joint Conferences on
Theory and Practice of Software.
MARS emphasises modelling over verification. It aims at discussing the
lessons learned from making formal methods for the verification and
analysis of realistic systems. Examples are:
(1) Which formalism is chosen, and why?
(2) Which abstractions have to be made and why?
(3) How are important characteristics of the system modelled?
(4) Were there any complications while modelling the system?
(5) Which measures were taken to guarantee the accuracy of the model?
We invited papers that present full models of real systems, which may
lay the basis for future comparison and analysis. An aim of the
workshop is to present different modelling approaches and discuss pros
and cons for each of them. Alternative formal descriptions of the
systems presented at this workshop are encouraged, which should foster
the development of improved specification formalisms.
VPT aims to provide a forum where people from the areas of program
transformation and program verification can fruitfully exchange ideas
and gain a deeper understanding of the interactions between those two
fields. These interactions have been beneficial in both directions. On
the one hand, methods and tools developed in the field of program
transformation, such as partial deduction, partial evaluation,
fold/unfold transformations, and supercompilation, are applied with
success to verification, in particular to the verification of infinite
state and parameterized systems. On the other hand, methods developed
in program verification, such as model checking, abstract
interpretation, SAT and SMT solving, and automated theorem proving,
are used to enhance program transformation techniques, thereby making
these techniques more powerful and useful in practice.
We develop and implement a translation from the process Algebra for Wireless Networks (AWN)
into the milli Common Representation Language (mCRL2). As a consequence of the translation,
the sophisticated toolset of mCRL2 is now available for AWNspecifications.
We show that the translation respects strong bisimilarity; hence all safety properties can be
automatically checked using the toolset. To show usability of our translation we report on a case study.
Keywords: process algebra; AWN; wireless mesh networks; mobile adhoc networks; routing protocols;
mCRL2; translation; bisimulation modulo renaming up to data congruence.
A mutual exclusion algorithm is called speed independent if
its correctness does not depend on the relative speed of the
components. Famous mutual exclusion protocols such as Dekker's,
Peterson's and Lamport's bakery are meant to be speed independent.
In this talk I argue that speedindependent mutual exclusion may not be
implementable on standard hardware, depending on how we believe
reading and writing to a memory location is really carried out. It can
be implemented on electrical circuits, however.
This builds on previous work showing that mutual exclusion
cannot be accurately modelled in standard process algebras.
Keywords: Mutual exclusion, speed independence,
concurrent reading and writing, liveness, justness.
Fairness assumptions are a valuable tool when reasoning about systems. In this paper, we
classify several fairness properties found in the literature and argue that most of them
are too restrictive for many applications. As an alternative we introduce the concept of justness.
Keywords:
Survey paper; Fairness, Progress, Justness, Liveness, Labelled Transition Systems.
In concurrency theory, weak bisimilarity is often used to relate processes
exhibiting the same observable behaviour. The probabilistic environment gives
rise to several generalisations; we study the infinitary semantics, which
abstracts from a potentially unbounded number of internal actions being
performed when something observable happens. Arguing that this notion yields the
most desirable properties, we provide a sound and complete axiomatisation
capturing its essence. Previous research has failed to achieve completeness in
the presence of unguarded recursion, as only the finitary variant has been
axiomatised, yet.
Keywords:
Axiomatisation, Process algebra, Probability, Recursion.
This paper poses that transition systems constitute a good
model of distributed systems only in combination with a criterion
telling which paths model complete runs of the represented systems.
Among such criteria, progress is too weak to capture relevant liveness
properties, and fairness is often too strong; for typical applications
we advocate the intermediate criterion of justness. Previously, we
proposed a definition of justness in terms of an asymmetric
concurrency relation between transitions. Here we define such a
concurrency relation for the transition systems associated to the
process algebra CCS as well as its extensions with broadcast
communication and signals, thereby making these process algebras
suitable for capturing liveness properties requiring justness.
Keywords: Justness, progress, fairness, completeness criteria, liveness,
distributed systems, process algebra, labelled transition systems with concurrency,
CCS, broadcast communication, signals.
 Available as
pdf and
sources.
 Archived at http://arxiv.org/abs/1909.00286.
 Extended abstract in: Proceedings 22st
International Conference on Foundations of Software Science
and Computation Structures (FoSSaCS 2019); held as part of
the European Joint Conferences on Theory and Practice of
Software (ETAPS 2019), Prague, Czech Republic, April 2019
(M. BojaĆczyk, A. Simpson, eds.), LNCS 11425,
Springer, pp. 505522, doi:10.1007/9783030171278_29.
 Extended abstract available as
pdf and
sources.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#135
We propose a process algebra for link layer protocols, featuring a unique
mechanism for modelling frame collisions. We also formalise suitable liveness
properties for link layer protocols specified in this framework. To show
applicability we model and analyse two versions of the CarrierSense Multiple
Access with Collision Avoidance (CSMA/CA) protocol. Our analysis confirms the
hidden station problem for the version without virtual carrier sensing.
However, we show that the version with virtual carrier sensing not only
overcomes this problem, but also the exposed station problem with probability 1.
Yet the protocol cannot guarantee packet delivery, not even with probability 1.
Keywords: Link layer protocols; CSMA/CA; virtual carrier sensing; packet delivery;
process algebra; ALL.
 Available as
pdf and
sources.
 Archived at http://arxiv.org/abs/1907.13329.
 In L. Caires, ed.: Programming Languages and Systems, Proceedings 28th
European Symposium on Programming (ESOP 2019); held as part of
the European Joint Conferences on Theory and Practice of
Software (ETAPS 2019), Prague, Czech Republic, April 2019,
LNCS 11423, Springer, pp. 668693,
doi:10.1007/9783030171841_24
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#136
May and must testing were introduced by De Nicola and Hennessy to
define semantic equivalences on processes. Maytesting equivalence
exactly captures safety properties, and musttesting equivalence
liveness properties. This paper proposes reward testing and shows that
the resulting semantic equivalence also captures conditional liveness
properties. It is strictly finer than both the may and musttesting equivalence.
Keywords: Reward testing, Semantic equivalences, Conditional liveness properties,
Labelled transition systems, Process algebra, CCS, Axiomatisations, Recursion,
Congruence, Divergence.
Dedication:
to Rocco De Nicola, on the occasion of his 65th birthday.
Rocco's work has been a source of inspiration to my own.
 Available as
pdf,
dvi,
ps and
sources.
 Archived at http://arxiv.org/abs/1907.13348.
 In: Models, Languages, and Tools for Concurrent and Distributed Programming,
Essays Dedicated to Rocco De Nicola on the Occasion of His 65th Birthday
(M. Boreale, F. Corradini, M. Loreti & R. Pugliese, eds.), LNCS 11665,
Springer, 2019, pp. 4570, doi:10.1007/9783030214852_5.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#137
Often fairness assumptions need to be made in order to establish
liveness properties of distributed systems, but in many situations
they lead to false conclusions.
This document presents a research agenda aiming at laying the
foundations of a theory of concurrency that is equipped to ensure
liveness properties of distributed systems without making fairness
assumptions. This theory will encompass process algebra, temporal
logic and semantic models.
The agenda also includes the development of a methodology and tools
that allow successful application of this theory to the specification,
analysis and verification of realistic distributed systems.
Contemporary process algebras and temporal logics fail to make
distinctions between systems of which one has a crucial liveness
property and the other does not, at least when assuming justness,
a strong progress property, but not assuming fairness.
Setting up an alternative framework involves giving up on identifying
strongly bisimilar systems, inventing new induction principles,
developing new axiomatic bases for process algebras and new congruence
formats for operational semantics, and creating matching treatments of
time and probability.
Even simple systems like fair schedulers or mutual exclusion protocols
cannot be accurately specified in standard process algebras (or Petri
nets) in the absence of fairness assumptions. Hence the work involves
the study of adequate language or model extensions, and their
expressive power.
Keywords: Liveness, fairness, justness, progress, distributed systems,
concurrency, process algebra, temporal logic, labelled transition systems,
Petri nets, semantic equivalences, strong bisimulation, fair schedulers,
mutual exclusion, expressiveness, routing protocols, wireless mesh networks,
structural operational semantics, probabilistic processes, realtime,
approximation induction principle, recursive specification principle.
Note: An earlier version of this paper appeared as xii.
Transition System Specifications provide programming and specification languages with a semantics.
They provide the meaning of a closed term as a process graph: a state in a labelled transition system.
At the same time they provide the meaning of an nary operator, or more generally
an open term with n free variables, as an nary operation on process graphs.
The classical way of doing this, the closedterm semantics, reduces the
meaning of an open term to the meaning of its closed instantiations. It makes the meaning of an
operator dependent on the context in which it is employed. Here I propose an alternative
process graph semantics of TSSs that does not suffer from this drawback.
Semantic equivalences on process graphs can be lifted to open terms conform either the closedterm
or the process graph semantics. For pure TSSs the latter is more discriminating.
I consider five sanity requirements on the semantics of programming and specification languages
equipped with a recursion construct: compositionality, applied to nary operators, recursion and
variables, invariance under αconversion, and the recursive definition principle, saying that
the meaning of a recursive call should be a solution of the corresponding recursion equations. I
establish that the satisfaction of four of these requirements under the closedterm semantics of a
TSS implies their satisfaction under the process graph semantics.
Keywords: Structural operational semantics, transition system specifications, open terms,
process graph semantics, compositionality.
We analyse two translations from the synchronous into the asynchronous πcalculus, both without choice,
that are often quoted as standard examples of valid encodings, showing that the asynchronous
πcalculus is just as expressive as the synchronous one.
We examine which of the quality criteria for encodings from the literature support the validity
of these translations. Moreover, we prove their validity according to much stronger
criteria than considered previously in the literature.
Keywords: Process calculi, expressiveness, translations, quality criteria for encodings, valid encodings,
compositionality, operational correspondence, semantic equivalences, asynchronous πcalculus.
Dedication:
This paper is dedicated to Catuscia Palamidessi, on the occasion of her birthday.
It has always been a big pleasure and inspiration to discuss with her.
Note: This paper contains the material of 129.
 Available as pdf,
ps and
sources.
 In: The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to
Security and Privacy — Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday,
(M.S. Alvim, K. Chatzikokolakis, C. Olarte & F. Valencia, eds.), LNCS 11760, Springer, 2019,
pp. 182205, doi:10.1007/9783030311759_11.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#141
This paper proposes a notion of branching bisimilarity for nondeterministic probabilistic processes. In
order to characterize the corresponding notion of rooted branching probabilistic bisimilarity, an equational theory is
proposed for a basic, recursionfree process language with nondeterministic as well as probabilistic choice. The proof
of completeness of the axiomatization builds on the completeness of strong probabilistic bisimilarity on the one hand
and on the notion of a concrete process, i.e. a process that does not display (partially) inert τmoves, on the other
hand. The approach is first presented for the nondeterministic fragment of the calculus and next generalized to
incorporate probabilistic choice, too.
Keywords: Process algebra, probabilistic processes, nondeterminism, branching bisimulation, complete axiomatisation.
Dedication:
to Catuscia Palamidessi, on the occasion of her 60th birthday.
 Available as pdf.
 In: The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to
Security and Privacy — Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday,
(M.S. Alvim, K. Chatzikokolakis, C. Olarte & F. Valencia, eds.), LNCS 11760, Springer, 2019,
pp. 139162, doi:10.1007/9783030311759_9.
 Full version available as pdf.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#142
In this paper, we consider the problem of crosschain payment whereby customers of different
escrows—implemented by a bank or a blockchain smart contract—successfully transfer digital
assets without trusting each other. Prior to this work, crosschain payment problems did not require this
success or any form of progress. We introduce a new specification formalism called Asynchronous Networks
of Timed Automata (ANTA) to formalise such protocols. We present the first crosschain payment protocol
that ensures termination in a bounded amount of time and works correctly in the presence of clock skew.
We then demonstrate that it is impossible to solve this problem without assuming synchrony, in the sense
that each message is guaranteed to arrive within a known amount of time. We also offer a protocol that
solves an eventually terminating variant of this crosschain payment problem without synchrony, and even
in the presence of Byzantine failures.
Keywords: Crosschain payment protocols, distributed systems, fault tolerance, blockchain, asynchronous networks
of timed automata, asynchronous communication, clock skew, safety and liveness properties, crosschain deals.
Note: A 3page summary of this paper appaers as 147.
This paper extends a standard process algebra with a timeout operator, thereby increasing its
absolute expressiveness, while remaining within the realm of untimed process algebra, in the sense
that the progress of time is not quantified. Trace and failures equivalence fail to be congruences
for this operator; their congruence closure is characterised as failure trace equivalence.
Keywords: Concurrency, process algebra, timeouts, priority, CCSP, labelled transition systems,
semantic equivalences, linear time, branching time, failure trace semantics,
absolute expressiveness, full abstraction, safety properties, may testing.
Routing protocol specifications are traditionally written in plain English.
Often this yields ambiguities, inaccuracies or even contradictions.
Formal methods techniques, such as process algebras, avoid these problems,
thus leading to more precise and verifiable descriptions of protocols.
In this paper we use the timed process algebra TAWN for modelling the
Optimised Link State Routing protocol (OLSR) version 2.
Keywords: Wireless mesh networks, mobile adhoc networks,
timed process algebra, AWN, routing protocols, OLSR.
In most presentations of ACP with guarded recursion, recursive
specifications are finite or infinite sets of recursion equations of
which the righthand sides are guarded terms. The completeness with
respect to bisimulation equivalence of the axioms of ACP with guarded
recursion has only been proved for the special case where recursive
specifications are finite sets of recursion equations of which the
righthand sides are guarded terms of a restricted form known as
linear terms. In this note, we widen this completeness result to the
general case.
Keywords: process algebra, guarded recursion, completeness,
infinitary conditional logic.
We consider the problem of crosschain payment whereby customers of different
escrows—implemented by a bank or a blockchain smart contract—successfully
transfer digital assets without trusting each other. Prior to this work,
crosschain payment problems did not require this success, or any form of progress.
We demonstrate that it is possible to solve this problem when assuming synchrony,
in the sense that each message is guaranteed to arrive within a known amount of
time, but impossible to solve without assuming synchrony. Yet, we solve a weaker
variant of this problem, where success is conditional on the patience of the
participants, without assuming synchrony, and in the presence of Byzantine failures.
We also discuss the relation with the recently defined crosschain deals.
Keywords: Crosschain payment protocols, distributed systems, fault tolerance, blockchain, asynchronous networks
of timed automata, asynchronous communication, clock skew, safety and liveness properties, crosschain deals.
Note: This is a 3page summary of 143.
 Available as pdf.
 Archived at http://arxiv.org/abs/2007.08152.
 In: Proceedings 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '20,
Virtual Event, USA, July 2020, pp. 579–581,
doi:10.1145/3350755.3400264.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#147
This paper introduces the counterpart of strong bisimilarity for labelled transition systems extended
with timeout transitions. It supports this concept through a modal characterisation, congruence
results for a standard process algebra with recursion, and a complete axiomatisation.
Keywords: Concurrency, process algebra, timeouts, CCSP, labelled transition systems,
reactive bisimulation semantics, modal characterisations, congruence, recursion, complete axiomatisations.
Whereas standard treatments of temporal logic are adequate for closed systems, having no
runtime interactions with their environment, they fall short for reactive systems,
interacting with their environments through synchronisation of actions.
This paper introduces reactive temporal logic, a form of temporal logic adapted
for the study of reactive systems. I illustrate its use by applying it to formulate definitions
of a fair scheduler, and of a correct mutual exclusion protocol. Previous definitions of these
concepts were conceptually much more involved or less precise, leading to debates on whether or not
a given protocol satisfies the implicit requirements.
Keywords: Concurrency, reactive systems, temporal logic, LTL, process algebra,
labelled transition systems, Kripke structures, Petri nets, fair schedulers, mutual exclusion.
For onesafe Petri nets or condition/eventsystems, a process as
defined by Carl Adam Petri provides a notion of a run of a system where causal
dependencies are reflected in terms of a partial order.
Goltz and Reisig have generalised this concept for nets where places carry
multiple tokens, by distinguishing tokens according to their causal history.
However, this socalled individual token interpretation is often
considered too detailed.
Here we identify a subclass of Petri nets, called structural conflict nets,
where no interplay between conflict and concurrency due to token multiplicity occurs.
For this subclass, we define abstract processes as equivalence classes of
GoltzReisig processes. We justify this approach by showing that
there is a largest abstract process if and only if the underlying net is
conflictfree with respect to a canonical notion of conflict.
Note: This paper continues and completes the work started in 89.
Together, these papers show that a structural conflict net is conflictfree if
and only if it has exactly one maximal run—formalised as a largest abstract process.
The "if" direction stems from 89, and "only if" is contributed here.
The results of this paper appeared before in 90. However, there they were
formulated differently, as in that paper we didn't have the canonical preorder $\sqsubseteq_1^\infty$
on GoltzReisig processes that is introduced here—inducing a partial order on
abstract processes—and thus neither the concept of a largest abstract process.
Our current proofs are conceptually much simpler than the ones in 90,
as they are carried out directly on abstract processes, rather than via the auxiliary concepts of BDruns and FSruns.
What is called "abstract process" above is called "BDprocess" in the abstracts of 89 and 152.
Keywords: Concurrency, Petri nets, PTsystems, causal semantics, processes.
Goltz and Reisig generalised Petri's concept of processes of onesafe Petri nets
to general nets where places carry multiple tokens.
BDprocesses are equivalence classes of GoltzReisig processes connected through the
swapping transformation of Best and Devillers; they can be considered as an alternative
representation of runs of nets.
Here we present an order respecting bijection between the BDprocesses and the FSprocesses
of a countable net, the latter being defined—in an analogous way—as equivalence classes of
firing sequences.
Using this, we show that a countable net without binary conflicts has a (unique) largest BDprocess.
Note: The result that a Petri net $N$ without binary conflicts has a largest BDprocess
was obtained in 151 for the special case that $N$ is a structural conflict net.
Here it is generalised to arbitrary countable nets. (It does not hold for arbitrary
uncountable nets, although 151 includes the case of uncountable structural conflict nets).
The above result appeared before in 90. However, there it was
formulated differently, as in that paper we didn't have the canonical preorder $\sqsubseteq_1^\infty$
on GoltzReisig processes that was introduced in 151—inducing a partial order on
BDprocesses—and thus neither the concept of a largest BDprocess.
Our current proofs are conceptually simpler than the ones in 90,
as they avoid the auxiliary concepts of BDruns and FSruns.
Keywords: Concurrency, Petri nets, PTsystems, causal semantics, processes.
 Available as
pdf,
ps and
source files.
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#152
This paper shows that the πcalculus with implicit matching is no more expressive than
CCS_{γ}, a variant of CCS in which the result of a synchronisation of two actions is
itself an action subject to relabelling or restriction, rather than the silent action τ.
This is done by exhibiting a compositional translation from the πcalculus with implicit
matching to CCS_{γ} that is valid up to strong barbed bisimilarity.
The full πcalculus can be similarly expressed in CCS_{γ} enriched with the
triggering operation of Meije.
I also show that these results cannot be recreated with CCS in the role of CCS_{γ},
not even up to reduction equivalence, and not even for the asynchronous πcalculus
without restriction or replication.
Keywords: Process calculi, expressiveness, πcalculus, CCS, mobility, translations, valid encodings,
compositionality, strong barbed bisimilarity.
 Available as
pdf,
 This abstract: http://theory.stanford.edu/~rvg/abstracts.html#153
This note formally defines the concept of coinductive validity of judgements, and contrasts it with
inductive validity. For both notions it shows how a judgement is valid iff it has a formal proof.
Finally, it defines and illustrates the notion of a proof by coinduction.
Keywords: Coinduction, Formal proof, Process Algebra.
We investigate how different fairness assumptions affect results concerning
lockfreedom, a typical liveness property targeted by session type systems.
We fix a minimal session calculus and systematically take into account all
known fairness assumptions, thereby identifying precisely three interesting and
semantically distinct notions of lockfreedom, all of which having a sound
session type system. We then show that, by using a general merge operator in an
otherwise standard approach to global session types, we obtain a session type
system complete for the strongest amongst those notions of lockfreedom, which
assumes only justness of execution paths, a minimal fairness assumption for concurrent systems.
Keywords: Session types, lockfreedom, fairness, justness, sound and complete type systems.
Only papers
2,
i,
7,
8,
9,
10,
11,
12,
13,
14,
16,
17,
18,
19,
20
and 21
are not available electronically through a link from this webpage.
SFBreports of the TU Munich (1923) can be obtained from:
The original version of my dissertation (17) can be ordered through me, and
costs $11 or 7 euro. The second edition can be ordered through your bookstore,
or from CWI.
The book 39 can be ordered through your bookstore, or
from CSLI, Stanford
University, CA 94305, USA.
All other papers are available through me (free).
Rob van Glabbeek
rvg@CS.Stanford.EDU