We report on yet another formalization of the Church-Rosser property in lambda-calculi, carried out with the proof environment Beluga. After the well-known proofs of confluence for beta-reduction in the untyped settings, with and without Takahashi's complete developments method, we concentrate on eta-reduction and obtain the result for beta-eta modularly. We further extend the analysis to typed-calculi, in particular System F. Finally, we investigate the idea of pursuing the encoding directly in Beluga's meta-logic, as well as the use of Beluga's logic programming engine to search for counterexamples.

More Church-Rosser Proofs in BELUGA / A. Momigliano, M. Sassella. - In: ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE. - ISSN 2075-2180. - 402:(2024), pp. 34-42. (Intervento presentato al 18. convegno International Workshop on Logical and Semantic Frameworks, with Applications (LSFA) and 10th Workshop on Horn Clauses for Verification and Synthesis (HCVS) : 1 through 2 July tenutosi a Roma nel 2023) [10.4204/EPTCS.402.6].

More Church-Rosser Proofs in BELUGA

A. Momigliano
Primo
;
2024

Abstract

We report on yet another formalization of the Church-Rosser property in lambda-calculi, carried out with the proof environment Beluga. After the well-known proofs of confluence for beta-reduction in the untyped settings, with and without Takahashi's complete developments method, we concentrate on eta-reduction and obtain the result for beta-eta modularly. We further extend the analysis to typed-calculi, in particular System F. Finally, we investigate the idea of pursuing the encoding directly in Beluga's meta-logic, as well as the use of Beluga's logic programming engine to search for counterexamples.
Settore INF/01 - Informatica
2024
24-apr-2024
https://arxiv.org/abs/2404.14921v1
Article (author)
File in questo prodotto:
File Dimensione Formato  
paper-3.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 150.32 kB
Formato Adobe PDF
150.32 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/1047908
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact