Dans les années quatre-vingts-dix, on a remarqué ce que l'isomorphisme de Curry-Howard peut être étendu à la logique classique. De nombreux calculs ont été développés pour constituer la base de cette extension. On étudie dans cette thèse quelques uns de ces calculs.<br />On étudie tout d'abord le $\lambda \mu$-calcul simplement typé de Parigot. Parigot a prouvé par des méthodes sémantiques que son calcul est fortement normalisable. Ensuite, David et Nour ont donné une preuve arithmétique de la normalisation forte de ce calcul avec la règle $\mu'$ (règle duale de $\mu$). Cependant, si l'on ajoute au $\lambda \mu \mu'$-calcul la règle de simplification $\rho$, la normalisation forte est perdu. On montre que le $\mu \mu' \rho$-calcul non-typé est faiblement normalisable, et que le $\lambda \mu \mu' \rho$-calcul typé est aussi faiblement normalisable. De plus, on examine les effets d'ajouter quelques autre règles de simplification.<br />On établi ensuite une borne de la longueur des séquences de réduction en $\lambda \mu \rho \theta$-calcul simplement typé.<br />Ce résultat est une extension de celui de Xi pour le $\lambda$-calcul simplement typé.<br />Dans le chapitre suivant on présente une preuve arithmétique de la normalisation forte du $\lambda$-calcul symétrique de Berardi et Barbanera.<br />Enfin, on établi des traductions entre le $\lambda$-calcul symétrique de Berardi et Barbanera et le $\lmts$-calcul, qui est le $\lmt$-calcul de Curien et Herbelin étendu avec une négation. (... qui est obtenu du $\lmt$-calcul de Curien et Herbelin par l'étendre avec une négation).
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00419492 |
| Date | 12 December 2007 |
| Creators | Battyanyi, Peter |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0016 seconds