Published: 12th August 2012
DOI: 10.4204/EPTCS.89
ISSN: 2075-2180

EPTCS 89

Proceedings Combined 19th International Workshop on
Expressiveness in Concurrency
and 9th Workshop on
Structured Operational Semantics
Newcastle upon Tyne, UK, September 3, 2012

Edited by: Bas Luttik and Michel A. Reniers

Preface
Bas Luttik and Michel A. Reniers
Invited Presentation: Applying automata and games to simply typed lambda calculus
Colin Stirling
1
On the specification of operations on the rational behaviour of systems
Marcello M. Bonsangue, Stefan Milius and Jurriaan Rot
3
Relaxed Operational Semantics of Concurrent Programming Languages
Gérard Boudol, Gustavo Petri and Bernard Serpette
19
Partially-commutative context-free languages
Wojciech Czerwiński and Sławomir Lasota
35
Expressiveness and Completeness in Abstraction
Maciej Gazda and Tim A.C. Willemse
49
Hide and New in the Pi-Calculus
Marco Giunti, Catuscia Palamidessi and Frank D. Valencia
65
Musings on Encodings and Expressiveness
Rob van Glabbeek
81
Approximating Weak Bisimilarity of Basic Parallel Processes
Piotr Hofman and Patrick Totzke
99
Tree rules in probabilistic transition system specifications with negative and quantitative premises
Matias David Lee, Daniel Gebler and Pedro R. D'Argenio
115
An Operational Petri Net Semantics for the Join-Calculus
Stephan Mennicke
131
Operational semantics for signal handling
Maxim Strygin and Hayo Thielecke
149

Preface

This volume contains the proceedings of the Combined 19th International Workshop on Expressiveness in Concurrency and the 9th Workshop on Structural Operational Semantics (EXPRESS/SOS 2012) which was held on September 3, 2012 in Newcastle upon Tyne, United Kingdom, as an affiliated workshop of CONCUR 2012, the 23th International Conference on Concurrency Theory.

The EXPRESS workshops aim at bringing together researchers interested in the expressiveness of various formal systems and semantic notions, particularly in the field of concurrency. Their focus has traditionally been on the comparison between programming concepts (such as concurrent, functional, imperative, logic and object-oriented programming) and between mathematical models of computation (such as process algebras, Petri nets, event structures, modal logics, and rewrite systems) on the basis of their relative expressive power. The EXPRESS workshop series has run successfully since 1994 and over the years this focus has become broadly construed.

The SOS workshops aim at being a forum for researchers, students and practitioners interested in new developments, and directions for future investigation, in the field of structural operational semantics. One of the specific goals of the SOS workshop series is to establish synergies between the concurrency and programming language communities working on the theory and practice of SOS. Reports on applications of SOS to other fields are also most welcome, including: modelling and analysis of biological systems, security of computer systems programming, modelling and analysis of embedded systems, specification of middle-ware and coordination languages, programming language semantics and implementation, static analysis software and hardware verification, and semantics for domain-specific languages and model-based engineering.

In 2012, the EXPRESS and SOS communities organized a combined EXPRESS/SOS 2012 workshop on the formal semantics of systems and programming concepts, and on the expressiveness of mathematical models of computation. We received seventeen submissions out of which the programme committee selected ten for presentation at the workshop. These proceedings contain these selected contributions. The workshop also had an invited presentation:

Applying automata and games to simply typed lambda calculus,
by Colin Stirling (University of Edinburgh, United Kingdom).

We would like to thank the authors of the submitted papers, the invited speaker, the members of the programme committee, and their subreviewers for their contribution to both the meeting and this volume. We also thank the CONCUR 2012 organizing committee for hosting EXPRESS/SOS 2012. Finally, we would like to thank our EPTCS editor Rob van Glabbeek for publishing these proceedings and his help during the preparation.

Bas Luttik and Michel A. Reniers,
Eindhoven, August 2012.

Programme Committee

Luca Aceto (Reykjavik, Iceland)
Johannes Borgström (Uppsala University, Sweden)
Ilaria Castellani (INRIA Sophia Antipolis, France)
Sibylle Fröschle (University of Oldenburg, Germany)
Fabio Gadducci (Università di Pisa, Italy)
Bartek Klin (University of Warsaw, Poland)
Bas Luttik (Eindhoven University of Technology, The Netherlands)
Keiko Nakata (Tallinn University of Technology, Estonia)
Michel Reniers (Eindhoven University of Technology, The Netherlands)
Jiří Srba (Aalborg University, Denmark)
Alwen Tiu (Australian National University, Australia)
Frank Valencia (LIX, CNRS & Ecole Polytechnique, France)
Walter Vogler (Augsburg University, Germany)

Additional Reviewers

Allan van Hulst
Hans Hüttel
Jasen Markovski
Mohammad Reza Mousavi
Willard Rafnsson
Frank Stappers
Mark Timmer
Louis-Marie Traonouez
Tjark Weber


Applying automata and games to simply typed lambda calculus

Colin Stirling (University of Edinburgh, United Kingdom)

The application of automata and games to verification of concurrent systems is now well established. In this talk we consider how automata and games can be used to solve decision problems in simply typed lambda calculus.