Strong normalisation in the π-calculus
File(s)DTR03-1.pdf (528.68 KB)
Published version
Author(s)
Yoshida, Nobuko
Berger, Martin
Honda, Kohei
Type
Report
Abstract
We introduce a typed π-calculus where strong normalisation is ensured by typability.
Strong normalisation is a useful property in many computational contexts,
including distributed systems. In spite of its simplicity, our type discipline captures
a wide class of converging name-passing interactive behaviour. The proof of
strong normalisability combines methods from typed λ-calculi and linear logic with
process-theoretic reasoning. It is adaptable to systems involving state, polymorphism
and other extensions. Strong normalisation is shown to have significant consequences,
including finite axiomatisation of weak bisimilarity, a fully abstract embedding
of the simply-typed λ-calculus with products and sums and basic liveness
in interaction. Strong normalisability has been extensively studied as a fundamental
property in functional calculi, term rewriting and logical systems. This work is one
of the first steps to extend theories and proof methods for strong normalisability to
the context of name-passing processes.
Strong normalisation is a useful property in many computational contexts,
including distributed systems. In spite of its simplicity, our type discipline captures
a wide class of converging name-passing interactive behaviour. The proof of
strong normalisability combines methods from typed λ-calculi and linear logic with
process-theoretic reasoning. It is adaptable to systems involving state, polymorphism
and other extensions. Strong normalisation is shown to have significant consequences,
including finite axiomatisation of weak bisimilarity, a fully abstract embedding
of the simply-typed λ-calculus with products and sums and basic liveness
in interaction. Strong normalisability has been extensively studied as a fundamental
property in functional calculi, term rewriting and logical systems. This work is one
of the first steps to extend theories and proof methods for strong normalisability to
the context of name-passing processes.
Date Issued
2003-01-01
Citation
Departmental Technical Report: 03/1, 2003, pp.1-55
Publisher
Department of Computing, Imperial College London
Start Page
1
End Page
55
Journal / Book Title
Departmental Technical Report: 03/1
Copyright Statement
© 2003 The Author(s). This report is available open access under a CC-BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Publication Status
Published
Article Number
03/1