A Strong Bisimulation for a Classical Term Calculus
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914901213052928 |
|---|---|
| author | Bonelli, Eduardo Kesner, Delia Viso, Andrés |
| author_facet | Bonelli, Eduardo Kesner, Delia Viso, Andrés |
| contents | When translating a term calculus into a graphical formalism many inessential details are abstracted away. In the case of $λ$-calculus translated to proof-nets, these inessential details are captured by a notion of equivalence on $λ$-terms known as $\simeq_σ$-equivalence, in both the intuitionistic (due to Regnier) and classical (due to Laurent) cases. The purpose of this paper is to uncover a strong bisimulation behind $\simeq_σ$-equivalence, as formulated by Laurent for Parigot's $λμ$-calculus. This is achieved by introducing a relation $\simeq$, defined over a revised presentation of $λμ$-calculus we dub $ΛM$.
More precisely, we first identify the reasons behind Laurent's $\simeq_σ$-equivalence on $λμ$-terms failing to be a strong bisimulation. Inspired by Laurent's \emph{Polarized Proof-Nets}, this leads us to distinguish multiplicative and exponential reduction steps on terms. Second, we enrich the syntax of $λμ$ to allow us to track the exponential operations. These technical ingredients pave the way towards a strong bisimulation for the classical case. We introduce a calculus $ΛM$ and a relation $\simeq$ that we show to be a strong bisimulation with respect to reduction in $ΛM$, ie. two $\simeq$-equivalent terms have the exact same reduction semantics, a result which fails for Regnier's $\simeq_σ$-equivalence in $λ$-calculus as well as for Laurent's $\simeq_σ$-equivalence in $λμ$. Although $\simeq$ is formulated over an enriched syntax and hence is not strictly included in Laurent's $\simeq_σ$, we show how it can be seen as a restriction of it. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2101_05754 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Strong Bisimulation for a Classical Term Calculus Bonelli, Eduardo Kesner, Delia Viso, Andrés Logic in Computer Science When translating a term calculus into a graphical formalism many inessential details are abstracted away. In the case of $λ$-calculus translated to proof-nets, these inessential details are captured by a notion of equivalence on $λ$-terms known as $\simeq_σ$-equivalence, in both the intuitionistic (due to Regnier) and classical (due to Laurent) cases. The purpose of this paper is to uncover a strong bisimulation behind $\simeq_σ$-equivalence, as formulated by Laurent for Parigot's $λμ$-calculus. This is achieved by introducing a relation $\simeq$, defined over a revised presentation of $λμ$-calculus we dub $ΛM$. More precisely, we first identify the reasons behind Laurent's $\simeq_σ$-equivalence on $λμ$-terms failing to be a strong bisimulation. Inspired by Laurent's \emph{Polarized Proof-Nets}, this leads us to distinguish multiplicative and exponential reduction steps on terms. Second, we enrich the syntax of $λμ$ to allow us to track the exponential operations. These technical ingredients pave the way towards a strong bisimulation for the classical case. We introduce a calculus $ΛM$ and a relation $\simeq$ that we show to be a strong bisimulation with respect to reduction in $ΛM$, ie. two $\simeq$-equivalent terms have the exact same reduction semantics, a result which fails for Regnier's $\simeq_σ$-equivalence in $λ$-calculus as well as for Laurent's $\simeq_σ$-equivalence in $λμ$. Although $\simeq$ is formulated over an enriched syntax and hence is not strictly included in Laurent's $\simeq_σ$, we show how it can be seen as a restriction of it. |
| title | A Strong Bisimulation for a Classical Term Calculus |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2101.05754 |