Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2311.04370 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909608025522176 |
|---|---|
| author | Battyanyi, Peter Nour, Karim |
| author_facet | Battyanyi, Peter Nour, Karim |
| contents | In this paper, we present a general realizability semantics for the simply typed $λμ$-calculus. Then, based on this semantics, we derive both weak and strong normalization results for two versions of the $λμ$-calculus equipped with specific simplification rules. The novelty in our method, in addition to its more systematic approach, lies in its applicability to a broader set of reduction rules without relying on the usual postponement technique. Our approach is original in that it introduces a parameter into the definition of the model, thus establishing a general result which we can then apply to systems with different sets of reduction rules by adjusting the parameter accordingly. Our saturation conditions also lead to a neat characterization of typable $λμ$-terms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_04370 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Normalization properties of $λμ$-calculus using realizability semantics Battyanyi, Peter Nour, Karim Logic 03B40, 03B70, 03F05, 68Q42 In this paper, we present a general realizability semantics for the simply typed $λμ$-calculus. Then, based on this semantics, we derive both weak and strong normalization results for two versions of the $λμ$-calculus equipped with specific simplification rules. The novelty in our method, in addition to its more systematic approach, lies in its applicability to a broader set of reduction rules without relying on the usual postponement technique. Our approach is original in that it introduces a parameter into the definition of the model, thus establishing a general result which we can then apply to systems with different sets of reduction rules by adjusting the parameter accordingly. Our saturation conditions also lead to a neat characterization of typable $λμ$-terms. |
| title | Normalization properties of $λμ$-calculus using realizability semantics |
| topic | Logic 03B40, 03B70, 03F05, 68Q42 |
| url | https://arxiv.org/abs/2311.04370 |