Book contents
- Frontmatter
- Contents
- List of contributors
- Preface
- 1 Determinacy in a synchronous π-calculus
- 2 Classical coordination mechanisms in the chemical model
- 3 Sequential algorithms as bistable maps
- 4 The semantics of dataflow with firing
- 5 Kahn networks at the dawn of functional programming
- 6 A simple type-theoretic language: Mini-TT
- 7 Program semantics and infinite regular terms
- 8 Algorithms for equivalence and reduction to minimal form for a class of simple recursive equations
- 9 Generalized finite developments
- 10 Semantics of program representation graphs
- 11 From Centaur to the Meta-Environment: a tribute to a great meta-technologist
- 12 Towards a theory of document structure
- 13 Grammars as software libraries
- 14 The Leordo computation system
- 15 Theorem-proving support in programming language semantics
- 16 Nominal verification of algorithm W
- 17 A constructive denotational semantics for Kahn networks in Coq
- 18 Asclepios: a research project team at INRIA for the analysis and simulation of biomedical images
- 19 Proxy caching in split TCP: dynamics, stability and tail asymptotics
- 20 Two-by-two static, evolutionary, and dynamic games
- 21 Reversal strategies for adjoint algorithms
- 22 Reflections on INRIA and the role of Gilles Kahn
- 23 Can a systems biologist fix a Tamagotchi?
- 24 Computational science: a new frontier for computing
- 25 The descendants of Centaur: a personal view on Gilles Kahn's work
- 26 The tower of informatic models
1 - Determinacy in a synchronous π-calculus
Published online by Cambridge University Press: 06 August 2010
- Frontmatter
- Contents
- List of contributors
- Preface
- 1 Determinacy in a synchronous π-calculus
- 2 Classical coordination mechanisms in the chemical model
- 3 Sequential algorithms as bistable maps
- 4 The semantics of dataflow with firing
- 5 Kahn networks at the dawn of functional programming
- 6 A simple type-theoretic language: Mini-TT
- 7 Program semantics and infinite regular terms
- 8 Algorithms for equivalence and reduction to minimal form for a class of simple recursive equations
- 9 Generalized finite developments
- 10 Semantics of program representation graphs
- 11 From Centaur to the Meta-Environment: a tribute to a great meta-technologist
- 12 Towards a theory of document structure
- 13 Grammars as software libraries
- 14 The Leordo computation system
- 15 Theorem-proving support in programming language semantics
- 16 Nominal verification of algorithm W
- 17 A constructive denotational semantics for Kahn networks in Coq
- 18 Asclepios: a research project team at INRIA for the analysis and simulation of biomedical images
- 19 Proxy caching in split TCP: dynamics, stability and tail asymptotics
- 20 Two-by-two static, evolutionary, and dynamic games
- 21 Reversal strategies for adjoint algorithms
- 22 Reflections on INRIA and the role of Gilles Kahn
- 23 Can a systems biologist fix a Tamagotchi?
- 24 Computational science: a new frontier for computing
- 25 The descendants of Centaur: a personal view on Gilles Kahn's work
- 26 The tower of informatic models
Summary
Abstract
The Sπ-calculus is a synchronous π-calculus which is based on the SL model. The latter is a relaxation of the Esterel model where the reaction to the absence of a signal within an instant can only happen at the next instant. In the present work, we present and characterize a compositional semantics of the Sπ-calculus based on suitable notions of labelled transition system and bisimulation. Based on this semantic framework, we explore the notion of determinacy and the related one of (local) confluence.
Introduction
Let P be a program that can repeatedly interact with its environment. A derivative of P is a program to which P reduces after a finite number of interactions with the environment. A program terminates if all its internal computations terminate and it is reactive if all its derivatives are guaranteed to terminate. A program is determinate if after any finite number of interactions with the environment the resulting derivative is unique up to semantic equivalence.
Most conditions found in the literature that entail determinacy are rather intuitive, however the formal statement of these conditions and the proof that they indeed guarantee determinacy can be rather intricate in particular in the presence of name mobility, as available in a paradigmatic form in the π-calculus.
Our purpose here is to provide a streamlined theory of determinacy for the synchronous π-calculus introduced in.
- Type
- Chapter
- Information
- From Semantics to Computer ScienceEssays in Honour of Gilles Kahn, pp. 1 - 28Publisher: Cambridge University PressPrint publication year: 2009