InforLorV4, Hal, Corpus, bibRecord, 005010

Type systems and deduction in the rewriting calculus

Identifieur interne : 005010 ( Hal/Corpus ); précédent : 005009; suivant : 005011

Type systems and deduction in the rewriting calculus

Auteurs : Benjamin Wack

Source :

RBID : Hal:tel-00010546

Descripteurs français

mix :
- Lambda-calcul, déduction, filtrage, principe de Poincaré, réécriture, typage.

English descriptors

mix :
- Lambda-calculus, Poincaré principle, pattern matching, rewriting, type systems.

Abstract

The rewriting calculus is a lambda-calculus with pattern matching. This thesis is devoted to the study of type systems for this calculus, and to its applications to the domain of deduction.

We study two typing paradigms. The first one is inspired by the simply typed lambda-calculus, but it differs from it in the sense that a term may be well-typed without being terminating. Thus, we use it for representing programs and rewriting systems.

The second family of type systems we study is adapted from the Pure Type Systems. We show its strong normalization via a translation into a typed lambda-calculus.

Finally, we propose two ways of using the rewriting calculus in logic. In the first approach, we use the strongly normalizing systems to define proof terms for deduction modulo. In the second case, we define a generalization of natural deduction and we show that matching is useful in order to represent the rules of this deduction system.

Url:

https://tel.archives-ouvertes.fr/tel-00010546

Links to Exploration step

Hal:tel-00010546

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Type systems and deduction in the rewriting calculus</title>
<title xml:lang="fr">Typage et déduction dans le calcul de réécriture</title>
<author><name sortKey="Wack, Benjamin" sort="Wack, Benjamin" uniqKey="Wack B" first="Benjamin" last="Wack">Benjamin Wack</name>
<affiliation><hal:affiliation type="researchteam" xml:id="struct-2360" status="OLD"><idno type="RNSR">199221357D</idno>
<orgName>Constraints, automatic deduction and software properties proofs</orgName>
<orgName type="acronym">PROTHEO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/protheo</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:tel-00010546</idno>
<idno type="halId">tel-00010546</idno>
<idno type="halUri">https://tel.archives-ouvertes.fr/tel-00010546</idno>
<idno type="url">https://tel.archives-ouvertes.fr/tel-00010546</idno>
<date when="2005-10-07">2005-10-07</date>
<idno type="wicri:Area/Hal/Corpus">005010</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Type systems and deduction in the rewriting calculus</title>
<title xml:lang="fr">Typage et déduction dans le calcul de réécriture</title>
<author><name sortKey="Wack, Benjamin" sort="Wack, Benjamin" uniqKey="Wack B" first="Benjamin" last="Wack">Benjamin Wack</name>
<affiliation><hal:affiliation type="researchteam" xml:id="struct-2360" status="OLD"><idno type="RNSR">199221357D</idno>
<orgName>Constraints, automatic deduction and software properties proofs</orgName>
<orgName type="acronym">PROTHEO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/protheo</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Lambda-calculus</term>
<term>Poincaré principle</term>
<term>pattern matching</term>
<term>rewriting</term>
<term>type systems</term>
</keywords>
<keywords scheme="mix" xml:lang="fr"><term>Lambda-calcul</term>
<term>déduction</term>
<term>filtrage</term>
<term>principe de Poincaré</term>
<term>réécriture</term>
<term>typage</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The rewriting calculus is a lambda-calculus with pattern matching. This thesis is devoted to the study of type systems for this calculus, and to its applications to the domain of deduction.

We study two typing paradigms. The first one is inspired by the simply typed lambda-calculus, but it differs from it in the sense that a term may be well-typed without being terminating. Thus, we use it for representing programs and rewriting systems.

The second family of type systems we study is adapted from the Pure Type Systems. We show its strong normalization via a translation into a typed lambda-calculus.

Finally, we propose two ways of using the rewriting calculus in logic. In the first approach, we use the strongly normalizing systems to define proof terms for deduction modulo. In the second case, we define a generalization of natural deduction and we show that matching is useful in order to represent the rules of this deduction system.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">Type systems and deduction in the rewriting calculus</title>
<title xml:lang="fr">Typage et déduction dans le calcul de réécriture</title>
<author role="aut"><persName><forename type="first">Benjamin</forename>
<surname>Wack</surname>
</persName>
<email></email>
<idno type="halauthor">70726</idno>
<affiliation ref="#struct-2360"></affiliation>
</author>
<editor role="depositor"><persName><forename>Benjamin</forename>
<surname>Wack</surname>
</persName>
<email>benjamin.wack@loria.fr</email>
</editor>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2005-10-11 17:43:42</date>
<date type="whenModified">2016-05-19 01:09:21</date>
<date type="whenReleased">2005-10-11 17:52:21</date>
<date type="whenProduced">2005-10-07</date>
<date type="whenEndEmbargoed">2005-10-11</date>
<ref type="file" target="https://tel.archives-ouvertes.fr/tel-00010546/document"><date notBefore="2005-10-11"></date>
</ref>
<ref type="file" n="1" target="https://tel.archives-ouvertes.fr/tel-00010546/file/tel-000105461.pdf"><date notBefore="2005-10-11"></date>
</ref>
<ref type="annex" subtype="other" n="0" target="https://tel.archives-ouvertes.fr/tel-00010546/file/tel-00010546.pdf"><date notBefore="2005-10-11"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="107107"><persName><forename>Benjamin</forename>
<surname>Wack</surname>
</persName>
<email>benjamin.wack@loria.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">tel-00010546</idno>
<idno type="halUri">https://tel.archives-ouvertes.fr/tel-00010546</idno>
<idno type="halBibtex">wack:tel-00010546</idno>
<idno type="halRefHtml">Autre [cs.OH]. Université Henri Poincaré - Nancy I, 2005. Français</idno>
<idno type="halRef">Autre [cs.OH]. Université Henri Poincaré - Nancy I, 2005. Français</idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno>
<idno type="stamp" n="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="LORIA-FM" p="LORIA">Méthodes formelles</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno>
</seriesStmt>
<notesStmt><note type="commentary">Président : Mariangiola Dezani
Rapporteurs : Gilles Dowek, Herman Geuvers
Examinateurs : Adam Cichon, Claude Kirchner, Luigi Liquori</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Type systems and deduction in the rewriting calculus</title>
<title xml:lang="fr">Typage et déduction dans le calcul de réécriture</title>
<author role="aut"><persName><forename type="first">Benjamin</forename>
<surname>Wack</surname>
</persName>
<idno type="halAuthorId">70726</idno>
<affiliation ref="#struct-2360"></affiliation>
</author>
</analytic>
<monogr><imprint><date type="dateDefended">2005-10-07</date>
</imprint>
<authority type="institution">Université Henri Poincaré - Nancy I</authority>
<authority type="supervisor">Kirchner Claude(ckirchne@loria.fr)</authority>
<authority type="jury">Liquori Luigi (co-directeur)</authority>
</monogr>
<ref type="seeAlso">http://www.loria.fr/~wack/these.pdf</ref>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="fr">French</language>
</langUsage>
<textClass><keywords scheme="author"><term xml:lang="en">Lambda-calculus</term>
<term xml:lang="en">rewriting</term>
<term xml:lang="en">pattern matching</term>
<term xml:lang="en">type systems</term>
<term xml:lang="en">Poincaré principle</term>
<term xml:lang="fr">Lambda-calcul</term>
<term xml:lang="fr">réécriture</term>
<term xml:lang="fr">filtrage</term>
<term xml:lang="fr">typage</term>
<term xml:lang="fr">déduction</term>
<term xml:lang="fr">principe de Poincaré</term>
</keywords>
<classCode scheme="halDomain" n="info.info-oh">Computer Science [cs]/Other [cs.OH]</classCode>
<classCode scheme="halTypology" n="THESE">Theses</classCode>
</textClass>
<abstract xml:lang="en">The rewriting calculus is a lambda-calculus with pattern matching. This thesis is devoted to the study of type systems for this calculus, and to its applications to the domain of deduction.

We study two typing paradigms. The first one is inspired by the simply typed lambda-calculus, but it differs from it in the sense that a term may be well-typed without being terminating. Thus, we use it for representing programs and rewriting systems.

The second family of type systems we study is adapted from the Pure Type Systems. We show its strong normalization via a translation into a typed lambda-calculus.

Finally, we propose two ways of using the rewriting calculus in logic. In the first approach, we use the strongly normalizing systems to define proof terms for deduction modulo. In the second case, we define a generalization of natural deduction and we show that matching is useful in order to represent the rules of this deduction system.</abstract>
<abstract xml:lang="fr">Le calcul de réécriture est un lambda-calcul avec filtrage. Cette thèse est consacrée à l'étude de systèmes de types pour ce calcul et à son utilisation dans le domaine de la déduction.

Nous étudions deux paradigmes de typage. Le premier est inspiré du lambda-calcul simplement typé, mais un terme peut y être typé sans être terminant. Nous l'utilisons donc pour représenter des programmes et des systèmes de réécriture. La seconde famille de systèmes de types que nous étudions est adaptée des Pure Type Systems. Nous en démontrons la normalisation forte grâce à une traduction vers le lambda-calcul typé.

Enfin nous proposons deux approches pour l'utilisation du calcul de réécriture en logique. La première consiste à définir des termes de preuve pour la déduction modulo à l'aide des systèmes fortement normalisants. Dans la seconde, nous définissons une généralisation de la déduction naturelle et nous montrons que le filtrage est utile pour représenter les règles de ce système de déduction.</abstract>
</profileDesc>
</hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005010 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 005010 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Hal
   |étape=   Corpus
   |type=    RBID
   |clé=     Hal:tel-00010546
   |texte=   Type systems and deduction in the rewriting calculus
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Type systems and deduction in the rewriting calculus

Type systems and deduction in the rewriting calculus

Source :

Descripteurs français

English descriptors

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri