A Beluga Formalization of the Harmony Lemma in the $π$-Calculus
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913422948433920 |
|---|---|
| author | Cecilia, Gabriele Momigliano, Alberto |
| author_facet | Cecilia, Gabriele Momigliano, Alberto |
| contents | The "Harmony Lemma", as formulated by Sangiorgi & Walker, establishes the equivalence between the labelled transition semantics and the reduction semantics in the $π$-calculus. Despite being a widely known and accepted result for the standard $π$-calculus, this assertion has never been rigorously proven, formally or informally. Hence, its validity may not be immediately apparent when considering extensions of the $π$-calculus. Contributing to the second challenge of the Concurrent Calculi Formalization Benchmark -- a set of challenges tackling the main issues related to the mechanization of concurrent systems -- we present a formalization of this result for the fragment of the $π$-calculus examined in the Benchmark. Our formalization is implemented in Beluga and draws inspiration from the HOAS formalization of the LTS semantics popularized by Honsell et al. In passing, we introduce a couple of useful encoding techniques for handling telescopes and lexicographic induction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_06624 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Beluga Formalization of the Harmony Lemma in the $π$-Calculus Cecilia, Gabriele Momigliano, Alberto Logic in Computer Science The "Harmony Lemma", as formulated by Sangiorgi & Walker, establishes the equivalence between the labelled transition semantics and the reduction semantics in the $π$-calculus. Despite being a widely known and accepted result for the standard $π$-calculus, this assertion has never been rigorously proven, formally or informally. Hence, its validity may not be immediately apparent when considering extensions of the $π$-calculus. Contributing to the second challenge of the Concurrent Calculi Formalization Benchmark -- a set of challenges tackling the main issues related to the mechanization of concurrent systems -- we present a formalization of this result for the fragment of the $π$-calculus examined in the Benchmark. Our formalization is implemented in Beluga and draws inspiration from the HOAS formalization of the LTS semantics popularized by Honsell et al. In passing, we introduce a couple of useful encoding techniques for handling telescopes and lexicographic induction. |
| title | A Beluga Formalization of the Harmony Lemma in the $π$-Calculus |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2407.06624 |