<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of tel-01746463</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-04T14:04:41+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="fr">Calcul de réécriture : fondements et applications</title>
            <author role="aut">
              <persName>
                <forename type="first">Horatiu</forename>
                <surname>Cirstea</surname>
              </persName>
              <email type="md5">5da991db2e0829c50451d5f9a30c5d6b</email>
              <email type="domain">loria.fr</email>
              <idno type="idhal" notation="numeric">830963</idno>
              <idno type="halauthorid" notation="string">117480-830963</idno>
              <idno type="IDREF">https://www.idref.fr/152362525</idno>
              <idno type="ORCID">https://orcid.org/0000-0001-5105-5931</idno>
              <affiliation ref="#struct-206040"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Thèses</forename>
                <surname>UL</surname>
              </persName>
              <email type="md5">802a29f1e309ab28a703dab5e0384d41</email>
              <email type="domain">univ-lorraine.fr</email>
            </editor>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2018-03-29 10:38:18</date>
              <date type="whenModified">2025-11-14 12:07:04</date>
              <date type="whenReleased">2018-03-29 10:38:18</date>
              <date type="whenProduced">2000-10-25</date>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="436959">
                <persName>
                  <forename>Thèses</forename>
                  <surname>UL</surname>
                </persName>
                <email type="md5">802a29f1e309ab28a703dab5e0384d41</email>
                <email type="domain">univ-lorraine.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">tel-01746463</idno>
            <idno type="halUri">https://hal.univ-lorraine.fr/tel-01746463</idno>
            <idno type="halBibtex">cirstea:tel-01746463</idno>
            <idno type="halRefHtml">Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 2000. Français. &lt;a target="_blank" href="https://www.theses.fr/2000NAN10087"&gt;&amp;#x27E8;NNT : 2000NAN10087&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 2000. Français. &amp;#x27E8;NNT : 2000NAN10087&amp;#x27E9;</idno>
            <availability status="restricted"/>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="LORIA2">Publications du LORIA</idno>
            <idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
            <idno type="stamp" n="LORIA">Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
            <idno type="stamp" n="THESES-UL">Thèses de doctorat soutenues à l'Université de Lorraine</idno>
            <idno type="stamp" n="AM2I-UL">Pôle scientifique Automatique, Mathématiques, Informatique et leurs Intéractions de l'Université de Lorraine</idno>
          </seriesStmt>
          <notesStmt>
            <note type="commentary">Texte intégral accessible uniquement aux membres de l'Université de Lorraine</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="fr">Calcul de réécriture : fondements et applications</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Horatiu</forename>
                    <surname>Cirstea</surname>
                  </persName>
                  <email type="md5">5da991db2e0829c50451d5f9a30c5d6b</email>
                  <email type="domain">loria.fr</email>
                  <idno type="idhal" notation="numeric">830963</idno>
                  <idno type="halauthorid" notation="string">117480-830963</idno>
                  <idno type="IDREF">https://www.idref.fr/152362525</idno>
                  <idno type="ORCID">https://orcid.org/0000-0001-5105-5931</idno>
                  <affiliation ref="#struct-206040"/>
                </author>
              </analytic>
              <monogr>
                <idno type="nnt">2000NAN10087</idno>
                <imprint>
                  <date type="dateDefended">2000-10-25</date>
                </imprint>
                <authority type="institution">Université Henri Poincaré - Nancy 1</authority>
                <authority type="school">IAEM - Ecole Doctorale Informatique, Automatique, Électronique - Électrotechnique, Mathématiques</authority>
                <authority type="supervisor">Claude Kirchner</authority>
                <authority type="jury">Guy Cousineau [Président]</authority>
                <authority type="jury">Nachum Dershowitz [Rapporteur]</authority>
                <authority type="jury">Thérèse Hardin [Rapporteur]</authority>
                <authority type="jury">François Lamarche [Rapporteur]</authority>
                <authority type="jury">Alexander Bockmayr</authority>
              </monogr>
              <ref type="esrFullText" target="http://docnum.univ-lorraine.fr/prive/SCD_T_2000_0087_CIRSTEA.pdf"/>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="fr">French</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="fr">Langages de programmation</term>
                <term xml:lang="fr"> Systèmes de (informatique)</term>
                <term xml:lang="fr">Réécriture</term>
                <term xml:lang="fr"> Lambda-calcul</term>
                <term xml:lang="fr">Calcul de réécriture </term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-oh">Computer Science [cs]/Other [cs.OH]</classCode>
              <classCode scheme="halTypology" n="THESE">Theses</classCode>
              <classCode scheme="halOldTypology" n="THESE">Theses</classCode>
              <classCode scheme="halTreeTypology" n="THESE">Theses</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>This thesis is devoted to the study of a calculus that describes the application of conditional rewriting rules and the obtained results at the same level of representation. We introduce the rewriting calculus, also called the rho-calculus, which generalizes the first order term rewriting and lambda-calculus, and makespossible the representation of the non-determinism. In our approach the abstraction operator as well as the application operator are objects of calculus. The result of a reduction in the rewriting calculus is either an empty set representing the application failure,  or a singleton representing a deterministic result, or a set having several elements representing a- not-deterministic choice of results. In this thesis we concentrate on the properties of the rewriting calculus where a syntactic matching is used in order to bind the variables to their currerit values. We define evaluation strategies ensuring the confluence of the calcalus and we show that these strategies become trivial for restrictioris of the generalrewriting calculus to simpler calculi like the lambda-calculus. The rewriting calculus is not terminating in the untyped case but the strong normalization is obtained for the simply typed calculus. In the rewriting calculus extended with an operator allowing to test the application failure we define terms representing innermost and outermost normalizations with respect to a set of rewriting rules. By using these terms, we obtain a natural and concise description of the conditional rewriting. Finally, starting from the representation of the conditional rewriting rules, we show how the rewriting calculus can be used to give a semantics to ELAN, a language based on the application of rewriting rules controlled by strategies.</p>
            </abstract>
            <abstract xml:lang="fr">
              <p>L'objet de cette thèse est l'étude d'un calcul permettant de décrire l'application de règles de réécriture conditionnelles et de représenter les résultats obtenus. Nous introduisons le calcul de réécriture, appelé aussi le rho-calcul, qui généralise la réécriture du premier ordre et le lambda-calcul tout en permettant d'exprimer le non-déterminisme. Dans notre approche, l'opérateur d'abstraction ainsi que l'opérateur d'application sont des objets du calcul. Le résultat d'une réduction dans le calcul de réécriture est soit un ensemble vide représentant l'échec de l'application, soit un singleton représentant un résultat déterministe,soit un ensemble ayant plusieurs éléments représentant un choix non-déterministe de résultats. Au cours de cette thèse nous nous concentrons sur les propriétés du calcul de réécriture utilisant un filtrage syntaxique pour lier les variables à leurs valeurs actuelles. Nous définissons des stratégies d'évaluation garantissant la confluence du calcul et nous montrons que ces stratégies deviennent trivialespour des restrictions du calcul de réécriture général à des calculs plus simples comme le lambda-calcul. Le calcul de réécriture n'est pas terminant dans le cas non-typé mais la terminaison forte est obtenue pour le calcul simplement typé.Dans le calcul de réécriture étendu par un opérateur permettant de tester l'échec de l'application nous définissons des termes représentant la normalisation innermost et outermost par rapport à un ensemble de règles de réécriture. En utilisant ces termes, nous obtenons un codage naturel et concis de la réécritureconditionnelle. Enfin, à partir de la représentation des règles de réécriture conditionnelles, nous montrons comment le calcul de réécriture peut être employé pour donner une sémantique au langage ELAN basé sur l'application de règles de réécriture contrôlées par des stratégies.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="laboratory" xml:id="struct-206040" status="VALID">
          <idno type="IdRef">067077927</idno>
          <idno type="ISNI">0000000121795429</idno>
          <idno type="RNSR">198912571S</idno>
          <idno type="IdUnivLorraine">[UL]RSI--</idno>
          <idno type="ROR">https://ror.org/02vnf0c38</idno>
          <orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
          <orgName type="acronym">LORIA</orgName>
          <date type="start">2012-01-01</date>
          <desc>
            <address>
              <addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.loria.fr</ref>
          </desc>
          <listRelation>
            <relation active="#struct-300009" type="direct"/>
            <relation active="#struct-411575" type="direct"/>
            <relation active="#struct-413289" type="direct"/>
            <relation name="UMR7503" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-300009" status="VALID">
          <idno type="ROR">https://ror.org/02kvxyf05</idno>
          <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"/>
            </address>
            <ref type="url">http://www.inria.fr/en/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-411575" status="VALID">
          <idno type="IdRef">184443237</idno>
          <idno type="ROR">https://ror.org/019tcpt25</idno>
          <orgName>CentraleSupélec</orgName>
          <desc>
            <address>
              <addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.centralesupelec.fr</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-413289" status="VALID">
          <idno type="IdRef">157040569</idno>
          <idno type="IdUnivLorraine">[UL]100--</idno>
          <idno type="ROR">https://ror.org/04vfs2w97</idno>
          <orgName>Université de Lorraine</orgName>
          <orgName type="acronym">UL</orgName>
          <date type="start">2012-01-01</date>
          <desc>
            <address>
              <addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.univ-lorraine.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</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"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>