We propose a notion of symmetric reduction for a system of proof nets for multiplicative Affine Logic with Mix. We prove that such a reduction has the strong normalization and Church-Rosser properties. A notion of irrelevance in a proof net is defined and the possibility of cancelling the irrelevant parts without erasing the entire net is taken as one of the correctness conditions. Therefore purely local cut-reductions are given, minimizing cancellation and suggesting a paradigm of "computation without garbage collection". Reconsidering Ketonen and Weyhrauch's decision procedure for affine logic, the use od the mix rule is related to the non-determinism of classical proof theory. The question arises whether these features of classical cut-elimination are really irreducible to the familiar paradigm of cut-elimination in intuitionistic and linea logic.
Two paradigms of logical computation in affine logic?
BELLIN, Gianluigi
2003-01-01
Abstract
We propose a notion of symmetric reduction for a system of proof nets for multiplicative Affine Logic with Mix. We prove that such a reduction has the strong normalization and Church-Rosser properties. A notion of irrelevance in a proof net is defined and the possibility of cancelling the irrelevant parts without erasing the entire net is taken as one of the correctness conditions. Therefore purely local cut-reductions are given, minimizing cancellation and suggesting a paradigm of "computation without garbage collection". Reconsidering Ketonen and Weyhrauch's decision procedure for affine logic, the use od the mix rule is related to the non-determinism of classical proof theory. The question arises whether these features of classical cut-elimination are really irreducible to the familiar paradigm of cut-elimination in intuitionistic and linea logic.File | Dimensione | Formato | |
---|---|---|---|
Two_paradigms.pdf
accesso aperto
Tipologia:
Documento in Post-print
Licenza:
Dominio pubblico
Dimensione
1.69 MB
Formato
Adobe PDF
|
1.69 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.