Termination by completion
Identifieur interne : 00DE15 ( Main/Curation ); précédent : 00DE14; suivant : 00DE16Termination by completion
Auteurs : Françoise Bellegarde [États-Unis] ; Pierre Lescanne [France]Source :
- Applicable Algebra in Engineering, Communication and Computing [ 0938-1279 ] ; 1990-09-01.
English descriptors
- KwdEn :
- Teeft :
- Assoc, Assoc endo, Bachmair, Bellegarde, Completion procedure, Completion procedures, Comput, Computer science, Confluent, Critical pair, Critical pairs, Data structure, Dershowitz, Endomorphism, Lecture notes, Lescanne, Lexicographic, Lexicographic path, Local confluence, Local cooperation, Natural numbers, Noetherian, Normal form, Operator symbols, Recursive, Recursive decomposition, Recursive path, Replacement property, Right lexicographic status, Rule assoc, Simplification orderings, Technical report, Termination, Transition rules, Transitive closure.
Abstract
Abstract: This paper presents a completion procedure for proving termination of term rewrite systems. It works as follows. Given a term rewrite systemR supposed to terminate and a term rewrite systemT used to transformR, the completion builds an auxiliary term rewrite systemS, the system transformed ofR byT. The termination ofS andT associated with a property called local cooperation implies the termination ofR. If the process terminates this provides a mechanical proof of the termination ofR.
Url:
DOI: 10.1007/BF01810293
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000899
- to stream Istex, to step Curation: Pour aller vers cette notice dans l'étape Curation :000894
- to stream Istex, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :003221
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :00E695
Links to Exploration step
ISTEX:275375A9F7EEA0915D41F0FCC1F0E92A9008168CLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Termination by completion</title>
<author><name sortKey="Bellegarde, Francoise" sort="Bellegarde, Francoise" uniqKey="Bellegarde F" first="Françoise" last="Bellegarde">Françoise Bellegarde</name>
</author>
<author><name sortKey="Lescanne, Pierre" sort="Lescanne, Pierre" uniqKey="Lescanne P" first="Pierre" last="Lescanne">Pierre Lescanne</name>
<affiliation><country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="laboratoire" n="5">Laboratoire lorrain de recherche en informatique et ses applications</orgName>
<orgName type="university">Université de Lorraine</orgName>
<orgName type="institution">Centre national de la recherche scientifique</orgName>
<orgName type="institution">Institut national de recherche en informatique et en automatique</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:275375A9F7EEA0915D41F0FCC1F0E92A9008168C</idno>
<date when="1990" year="1990">1990</date>
<idno type="doi">10.1007/BF01810293</idno>
<idno type="url">https://api.istex.fr/ark:/67375/1BB-G4WFB6XR-Z/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000899</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000899</idno>
<idno type="wicri:Area/Istex/Curation">000894</idno>
<idno type="wicri:Area/Istex/Checkpoint">003221</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">003221</idno>
<idno type="wicri:doubleKey">0938-1279:1990:Bellegarde F:termination:by:completion</idno>
<idno type="wicri:Area/Main/Merge">00E695</idno>
<idno type="wicri:Area/Main/Curation">00DE15</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Termination by completion</title>
<author><name sortKey="Bellegarde, Francoise" sort="Bellegarde, Francoise" uniqKey="Bellegarde F" first="Françoise" last="Bellegarde">Françoise Bellegarde</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Western Washington University, 98225, Bellingham, WA</wicri:regionArea>
<placeName><region type="state">Washington (État)</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lescanne, Pierre" sort="Lescanne, Pierre" uniqKey="Lescanne P" first="Pierre" last="Lescanne">Pierre Lescanne</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>Centre de Recherche en Informatique de Nancy, CNRS and INRIA-Lorraine, Domaine Scientifique Victor Grignard, BP 239, F-54506, Vandœuvre-lès-Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="laboratoire" n="5">Laboratoire lorrain de recherche en informatique et ses applications</orgName>
<orgName type="university">Université de Lorraine</orgName>
<orgName type="institution">Centre national de la recherche scientifique</orgName>
<orgName type="institution">Institut national de recherche en informatique et en automatique</orgName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Applicable Algebra in Engineering, Communication and Computing</title>
<title level="j" type="abbrev">AAECC</title>
<idno type="ISSN">0938-1279</idno>
<idno type="eISSN">1432-0622</idno>
<imprint><publisher>Springer-Verlag</publisher>
<pubPlace>Berlin/Heidelberg</pubPlace>
<date type="published" when="1990-09-01">1990-09-01</date>
<biblScope unit="volume">1</biblScope>
<biblScope unit="issue">2</biblScope>
<biblScope unit="page" from="79">79</biblScope>
<biblScope unit="page" to="96">96</biblScope>
</imprint>
<idno type="ISSN">0938-1279</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0938-1279</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Completion</term>
<term>Term rewriting</term>
<term>Termination</term>
<term>Well-foundedness</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Assoc</term>
<term>Assoc endo</term>
<term>Bachmair</term>
<term>Bellegarde</term>
<term>Completion procedure</term>
<term>Completion procedures</term>
<term>Comput</term>
<term>Computer science</term>
<term>Confluent</term>
<term>Critical pair</term>
<term>Critical pairs</term>
<term>Data structure</term>
<term>Dershowitz</term>
<term>Endomorphism</term>
<term>Lecture notes</term>
<term>Lescanne</term>
<term>Lexicographic</term>
<term>Lexicographic path</term>
<term>Local confluence</term>
<term>Local cooperation</term>
<term>Natural numbers</term>
<term>Noetherian</term>
<term>Normal form</term>
<term>Operator symbols</term>
<term>Recursive</term>
<term>Recursive decomposition</term>
<term>Recursive path</term>
<term>Replacement property</term>
<term>Right lexicographic status</term>
<term>Rule assoc</term>
<term>Simplification orderings</term>
<term>Technical report</term>
<term>Termination</term>
<term>Transition rules</term>
<term>Transitive closure</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: This paper presents a completion procedure for proving termination of term rewrite systems. It works as follows. Given a term rewrite systemR supposed to terminate and a term rewrite systemT used to transformR, the completion builds an auxiliary term rewrite systemS, the system transformed ofR byT. The termination ofS andT associated with a property called local cooperation implies the termination ofR. If the process terminates this provides a mechanical proof of the termination ofR.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00DE15 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 00DE15 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Curation |type= RBID |clé= ISTEX:275375A9F7EEA0915D41F0FCC1F0E92A9008168C |texte= Termination by completion }}
This area was generated with Dilib version V0.6.33. |