An hierarchy of terminating algorithms with semantic interpretation termination proofs
Identifieur interne : 00B653 ( Main/Merge ); précédent : 00B652; suivant : 00B654An hierarchy of terminating algorithms with semantic interpretation termination proofs
Auteurs : Jean-Yves MarionSource :
English descriptors
Abstract
We study deterministic (non-deterministic) algorithms define by mean of confluent (resp. non-confluent) rewrite system admitting polynomial interpretation termination proofs. Data structures of the algorithms include strings, lists and trees. We classify them according to the interpretations of constructors This leads to the definition of six classes, which turn out to be exactly the deterministic (non-deterministic) poly-time, linear exponential-time and doubly linear exponential time computable functions when the class is based on confluent (resp. non-confluent) systems. Next, we demonstrate that functions with exponential interpretation termination proofs are super-elementary.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 002330
- to stream Crin, to step Curation: 002330
- to stream Crin, to step Checkpoint: 002180
Links to Exploration step
CRIN:marion98aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="686">An hierarchy of terminating algorithms with semantic interpretation termination proofs</title></titleStmt><publicationStmt><idno type="RBID">CRIN:marion98a</idno><date when="1998" year="1998">1998</date><idno type="wicri:Area/Crin/Corpus">002330</idno><idno type="wicri:Area/Crin/Curation">002330</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">002330</idno><idno type="wicri:Area/Crin/Checkpoint">002180</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">002180</idno><idno type="wicri:Area/Main/Merge">00B653</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">An hierarchy of terminating algorithms with semantic interpretation termination proofs</title><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>rewriting polynomial-interpretations computational-complexity</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="2678">We study deterministic (non-deterministic) algorithms define by mean of confluent (resp. non-confluent) rewrite system admitting polynomial interpretation termination proofs. Data structures of the algorithms include strings, lists and trees. We classify them according to the interpretations of constructors This leads to the definition of six classes, which turn out to be exactly the deterministic (non-deterministic) poly-time, linear exponential-time and doubly linear exponential time computable functions when the class is based on confluent (resp. non-confluent) systems. Next, we demonstrate that functions with exponential interpretation termination proofs are super-elementary.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B653 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00B653 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= CRIN:marion98a
|texte= An hierarchy of terminating algorithms with semantic interpretation termination proofs
}}
| This area was generated with Dilib version V0.6.33. |  |