Analysing the implicit complexity of programs
Identifieur interne : 007F82 ( Main/Merge ); précédent : 007F81; suivant : 007F83Analysing the implicit complexity of programs
Auteurs : J. Y. Marion [France]Source :
- Information and computation : (Print) [ 0890-5401 ] ; 2003.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
We study termination proofs in order to (i) determine computational complexity of programs and (ii) generate efficient programs from the complexity analysis. For this, we construct a termination ordering, called light multiset path ordering (LMPO), which is a restriction of the multiset path ordering. We establish that the class of first order functional programs on lists which is terminating by LMPO characterises exactly the functions computable in polynomial time.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000764
- to stream PascalFrancis, to step Curation: 000279
- to stream PascalFrancis, to step Checkpoint: 000723
Links to Exploration step
Pascal:03-0426819Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Analysing the implicit complexity of programs</title><author><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J. Y." last="Marion">J. Y. Marion</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria Calligramme Project B.P. 239</s1><s2>54506 Vandoeuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><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></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">03-0426819</idno><date when="2003">2003</date><idno type="stanalyst">PASCAL 03-0426819 INIST</idno><idno type="RBID">Pascal:03-0426819</idno><idno type="wicri:Area/PascalFrancis/Corpus">000764</idno><idno type="wicri:Area/PascalFrancis/Curation">000279</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000723</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000723</idno><idno type="wicri:doubleKey">0890-5401:2003:Marion J:analysing:the:implicit</idno><idno type="wicri:Area/Main/Merge">007F82</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Analysing the implicit complexity of programs</title><author><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J. Y." last="Marion">J. Y. Marion</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria Calligramme Project B.P. 239</s1><s2>54506 Vandoeuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><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></affiliation></author></analytic><series><title level="j" type="main">Information and computation : (Print)</title><title level="j" type="abbreviated">Inf. comput. : (Print)</title><idno type="ISSN">0890-5401</idno><imprint><date when="2003">2003</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Information and computation : (Print)</title><title level="j" type="abbreviated">Inf. comput. : (Print)</title><idno type="ISSN">0890-5401</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computational complexity</term><term>Computer theory</term><term>First order</term><term>Functional programming</term><term>Implicit theory</term><term>Multiset path ordering</term><term>Polynomial time</term><term>Program analysis</term><term>Program complexity</term><term>Rewriting systems</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term><term>Complexité calcul</term><term>Théorie implicite</term><term>Analyse programme</term><term>Complexité programme</term><term>Temps polynomial</term><term>Programmation fonctionnelle</term><term>Ordre 1</term><term>Système réécriture</term><term>Relation ordre chemin ensemble multiple</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We study termination proofs in order to (i) determine computational complexity of programs and (ii) generate efficient programs from the complexity analysis. For this, we construct a termination ordering, called light multiset path ordering (LMPO), which is a restriction of the multiset path ordering. We establish that the class of first order functional programs on lists which is terminating by LMPO characterises exactly the functions computable in polynomial time.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Vandœuvre-lès-Nancy</li></settlement></list><tree><country name="France"><region name="Grand Est"><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J. Y." last="Marion">J. Y. Marion</name></region></country></tree></affiliations></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 007F82 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 007F82 | 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é= Pascal:03-0426819
|texte= Analysing the implicit complexity of programs
}}
| This area was generated with Dilib version V0.6.33. |  |