Aspects typés du calcul de réécriture
Identifieur interne : 006C54 ( Hal/Curation ); précédent : 006C53; suivant : 006C55Aspects typés du calcul de réécriture
Auteurs : Benjamin Wack [France]Source :
Descripteurs français
- mix :
Abstract
Le calcul de réécriture intègre dans un même système le lambda-calcul et la réécriture. Pour cela, les abstractions ne se font plus seulement sur des variables mais sur des motifs. On profite ainsi à la fois des mécanismes d'ordre supérieur du lambda-calcul et de l'expressivité du filtrage de la réécriture. Nous nous intéressons ici au rho-calcul en tant qu'extension du lambda-calcul et nous en étudions les aspects typés, l'objectif étant de mieux comprendre les relations entre ce calcul et les systèmes logiques et ainsi d'étendre l'isomorphisme de Curry-Howard. Notre étude se base sur une généralisation du cube de Barendregt, où les deux abstracteurs lambda et Pi sont unifiés en un seul. Il nous faut aussi tenir compte des nouveaux éléments du rho-calcul. Sous les bonnes conditions, nous parvenons ainsi à prouver la plupart des propriétés habituelles des calculs typés. Cependant, l'unicité du type n'est généralement plus valable, notamment à cause de l'unification des abstracteurs. Nous prouvons que l'unicité reste valide dans les deux systèmes les plus simples.
Url:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :006C54
Links to Exploration step
Hal:inria-00099418Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="ro">Aspects typés du calcul de réécriture</title>
<author><name sortKey="Wack, Benjamin" sort="Wack, Benjamin" uniqKey="Wack B" first="Benjamin" last="Wack">Benjamin Wack</name>
<affiliation wicri:level="1"><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>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00099418</idno>
<idno type="halId">inria-00099418</idno>
<idno type="halUri">https://hal.inria.fr/inria-00099418</idno>
<idno type="url">https://hal.inria.fr/inria-00099418</idno>
<date when="2002">2002</date>
<idno type="wicri:Area/Hal/Corpus">006C54</idno>
<idno type="wicri:Area/Hal/Curation">006C54</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="ro">Aspects typés du calcul de réécriture</title>
<author><name sortKey="Wack, Benjamin" sort="Wack, Benjamin" uniqKey="Wack B" first="Benjamin" last="Wack">Benjamin Wack</name>
<affiliation wicri:level="1"><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>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>barendergt's cube</term>
<term>calcul de réécriture</term>
<term>cube de barendregt</term>
<term>lambda calcul</term>
<term>lambda calculus</term>
<term>rewriting</term>
<term>rewriting calculus</term>
<term>réécriture</term>
<term>théorie des types</term>
<term>type theory</term>
<term>type uniqueness</term>
<term>unicité du type</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="fr">Le calcul de réécriture intègre dans un même système le lambda-calcul et la réécriture. Pour cela, les abstractions ne se font plus seulement sur des variables mais sur des motifs. On profite ainsi à la fois des mécanismes d'ordre supérieur du lambda-calcul et de l'expressivité du filtrage de la réécriture. Nous nous intéressons ici au rho-calcul en tant qu'extension du lambda-calcul et nous en étudions les aspects typés, l'objectif étant de mieux comprendre les relations entre ce calcul et les systèmes logiques et ainsi d'étendre l'isomorphisme de Curry-Howard. Notre étude se base sur une généralisation du cube de Barendregt, où les deux abstracteurs lambda et Pi sont unifiés en un seul. Il nous faut aussi tenir compte des nouveaux éléments du rho-calcul. Sous les bonnes conditions, nous parvenons ainsi à prouver la plupart des propriétés habituelles des calculs typés. Cependant, l'unicité du type n'est généralement plus valable, notamment à cause de l'unification des abstracteurs. Nous prouvons que l'unicité reste valide dans les deux systèmes les plus simples.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="ro">Aspects typés du calcul de réécriture</title>
<author role="aut"><persName><forename type="first">Benjamin</forename>
<surname>Wack</surname>
</persName>
<email>wack@loria.fr</email>
<idno type="halauthor">130575</idno>
<orgName ref="#struct-6818"></orgName>
<affiliation ref="#struct-2360"></affiliation>
</author>
<editor role="depositor"><persName><forename>Publications</forename>
<surname>Loria</surname>
</persName>
<email>publications@loria.fr</email>
</editor>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2006-09-26 09:02:47</date>
<date type="whenModified">2016-05-19 01:09:32</date>
<date type="whenReleased">2006-09-28 15:22:46</date>
<date type="whenProduced">2002</date>
<date type="whenEndEmbargoed">2015-02-10</date>
<ref type="file" target="https://hal.inria.fr/inria-00099418/document"><date notBefore="2015-02-10"></date>
</ref>
<ref type="file" n="1" target="https://hal.inria.fr/inria-00099418/file/A02-R-175.pdf"><date notBefore="2015-02-10"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="108626"><persName><forename>Publications</forename>
<surname>Loria</surname>
</persName>
<email>publications@loria.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">inria-00099418</idno>
<idno type="halUri">https://hal.inria.fr/inria-00099418</idno>
<idno type="halBibtex">wack:inria-00099418</idno>
<idno type="halRefHtml">[Stage] A02-R-175 || wack02a, 2002, 44 p</idno>
<idno type="halRef">[Stage] A02-R-175 || wack02a, 2002, 44 p</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-FM" p="LORIA">Méthodes formelles</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</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">Stage de DEA. Rapport de stage.</note>
<note type="audience" n="0">Not set</note>
<note type="report" n="5">Intership report</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="ro">Aspects typés du calcul de réécriture</title>
<author role="aut"><persName><forename type="first">Benjamin</forename>
<surname>Wack</surname>
</persName>
<email>wack@loria.fr</email>
<idno type="halAuthorId">130575</idno>
<orgName ref="#struct-6818"></orgName>
<affiliation ref="#struct-2360"></affiliation>
</author>
</analytic>
<monogr><idno type="reportNumber">A02-R-175 || wack02a</idno>
<imprint><biblScope unit="pp">44 p</biblScope>
<date type="datePub">2002</date>
</imprint>
</monogr>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="fr">French</language>
</langUsage>
<textClass><keywords scheme="author"><term xml:lang="fr">calcul de réécriture</term>
<term xml:lang="fr">type uniqueness</term>
<term xml:lang="fr">rewriting calculus</term>
<term xml:lang="fr">rewriting</term>
<term xml:lang="fr">lambda calculus</term>
<term xml:lang="fr">type theory</term>
<term xml:lang="fr">barendergt's cube</term>
<term xml:lang="fr">réécriture</term>
<term xml:lang="fr">lambda calcul</term>
<term xml:lang="fr">théorie des types</term>
<term xml:lang="fr">cube de barendregt</term>
<term xml:lang="fr">unicité du type</term>
</keywords>
<classCode scheme="halDomain" n="info.info-oh">Computer Science [cs]/Other [cs.OH]</classCode>
<classCode scheme="halTypology" n="REPORT">Reports</classCode>
</textClass>
<abstract xml:lang="fr">Le calcul de réécriture intègre dans un même système le lambda-calcul et la réécriture. Pour cela, les abstractions ne se font plus seulement sur des variables mais sur des motifs. On profite ainsi à la fois des mécanismes d'ordre supérieur du lambda-calcul et de l'expressivité du filtrage de la réécriture. Nous nous intéressons ici au rho-calcul en tant qu'extension du lambda-calcul et nous en étudions les aspects typés, l'objectif étant de mieux comprendre les relations entre ce calcul et les systèmes logiques et ainsi d'étendre l'isomorphisme de Curry-Howard. Notre étude se base sur une généralisation du cube de Barendregt, où les deux abstracteurs lambda et Pi sont unifiés en un seul. Il nous faut aussi tenir compte des nouveaux éléments du rho-calcul. Sous les bonnes conditions, nous parvenons ainsi à prouver la plupart des propriétés habituelles des calculs typés. Cependant, l'unicité du type n'est généralement plus valable, notamment à cause de l'unification des abstracteurs. Nous prouvons que l'unicité reste valide dans les deux systèmes les plus simples.</abstract>
</profileDesc>
</hal>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006C54 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Curation/biblio.hfd -nk 006C54 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Hal |étape= Curation |type= RBID |clé= Hal:inria-00099418 |texte= Aspects typés du calcul de réécriture }}
This area was generated with Dilib version V0.6.33. |