Efficient first order functional program interpreter with time bound certifications
Identifieur interne : 00A612 ( Main/Merge ); précédent : 00A611; suivant : 00A613Efficient first order functional program interpreter with time bound certifications
Auteurs : Jean-Yves Marion [France] ; J.-Y. Moyen [France]Source :
- Lecture notes in computer science [ 0302-9743 ] ; 2000.
Descripteurs français
- Pascal (Inist)
English descriptors
Abstract
We demonstrate that the class of functions computed by first order functional programs over lists which terminate by multiset path ordering and admit a polynomial quasi-interpretation, is exactly the class of function computable in polynomial time. The interest of this result lies on (i) the simplicity of the conditions on programs to certify their complexity, (ii) the fact that an important class of natural programs is captured, (iii) potential applications for program optimisation.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000998
- to stream PascalFrancis, to step Curation: 000078
- to stream PascalFrancis, to step Checkpoint: 000A06
Links to Exploration step
Pascal:01-0016202Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Efficient first order functional program interpreter with time bound certifications</title><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 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><author><name sortKey="Moyen, J Y" sort="Moyen, J Y" uniqKey="Moyen J" first="J.-Y." last="Moyen">J.-Y. Moyen</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 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">01-0016202</idno><date when="2000">2000</date><idno type="stanalyst">PASCAL 01-0016202 INIST</idno><idno type="RBID">Pascal:01-0016202</idno><idno type="wicri:Area/PascalFrancis/Corpus">000998</idno><idno type="wicri:Area/PascalFrancis/Curation">000078</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000A06</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A06</idno><idno type="wicri:doubleKey">0302-9743:2000:Marion J:efficient:first:order</idno><idno type="wicri:Area/Main/Merge">00A612</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Efficient first order functional program interpreter with time bound certifications</title><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 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><author><name sortKey="Moyen, J Y" sort="Moyen, J Y" uniqKey="Moyen J" first="J.-Y." last="Moyen">J.-Y. Moyen</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Loria, Calligramme project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 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">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno><imprint><date when="2000">2000</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>First order</term><term>Functional programming</term><term>Interpreter</term><term>Metalanguage</term><term>Polynomial time</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Interpréteur</term><term>Programmation fonctionnelle</term><term>Ordre 1</term><term>Métalangage</term><term>Temps polynomial</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We demonstrate that the class of functions computed by first order functional programs over lists which terminate by multiset path ordering and admit a polynomial quasi-interpretation, is exactly the class of function computable in polynomial time. The interest of this result lies on (i) the simplicity of the conditions on programs to certify their complexity, (ii) the fact that an important class of natural programs is captured, (iii) potential applications for program optimisation.</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, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></region><name sortKey="Moyen, J Y" sort="Moyen, J Y" uniqKey="Moyen J" first="J.-Y." last="Moyen">J.-Y. Moyen</name></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 00A612 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00A612 | 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:01-0016202
|texte= Efficient first order functional program interpreter with time bound certifications
}}
| This area was generated with Dilib version V0.6.33. |  |