InforLorV4, Main, Exploration, bibRecord, 003064

Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity

Identifieur interne : 003064 ( Main/Exploration ); précédent : 003063; suivant : 003065

Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity

Auteurs : Hugo Férée [France] ; Emmanuel Hainry [France] ; Mathieu Hoyrup [France] ; Romain Péchoux [France]

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:5EEB206F6262CC894E2DA85530DB2F5A417619C5

Abstract

Abstract: We study polynomial time complexity of type 2 functionals. For that purpose, we introduce a first order functional stream language. We give criteria, named well-founded, on such programs relying on second order interpretation that characterize two variants of type 2 polynomial complexity including the Basic Feasible Functions (BFF). These characterizations provide a new insight on the complexity of stream programs. Finally, we adapt these results to functions over the reals, a particular case of type 2 functions, and we provide a characterization of polynomial time complexity in Recursive Analysis.

Url:

https://api.istex.fr/ark:/67375/HCB-8X9NQQNS-L/fulltext.pdf

DOI: 10.1007/978-3-642-17517-6_27

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Istex, to step Corpus: 001604
to stream Istex, to step Curation: 001585
to stream Istex, to step Checkpoint: 000826
to stream Main, to step Merge: 003121
to stream Main, to step Curation: 003064

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity</title>
<author><name sortKey="Feree, Hugo" sort="Feree, Hugo" uniqKey="Feree H" first="Hugo" last="Férée">Hugo Férée</name>
</author>
<author><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name>
</author>
<author><name sortKey="Hoyrup, Mathieu" sort="Hoyrup, Mathieu" uniqKey="Hoyrup M" first="Mathieu" last="Hoyrup">Mathieu Hoyrup</name>
</author>
<author><name sortKey="Pechoux, Romain" sort="Pechoux, Romain" uniqKey="Pechoux R" first="Romain" last="Péchoux">Romain Péchoux</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:5EEB206F6262CC894E2DA85530DB2F5A417619C5</idno>
<date when="2010" year="2010">2010</date>
<idno type="doi">10.1007/978-3-642-17517-6_27</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-8X9NQQNS-L/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001604</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001604</idno>
<idno type="wicri:Area/Istex/Curation">001585</idno>
<idno type="wicri:Area/Istex/Checkpoint">000826</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000826</idno>
<idno type="wicri:doubleKey">0302-9743:2010:Feree H:interpretation:of:stream</idno>
<idno type="wicri:Area/Main/Merge">003121</idno>
<idno type="wicri:Area/Main/Curation">003064</idno>
<idno type="wicri:Area/Main/Exploration">003064</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity</title>
<author><name sortKey="Feree, Hugo" sort="Feree, Hugo" uniqKey="Feree H" first="Hugo" last="Férée">Hugo Férée</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>ENS Lyon, 46 allée d’Italie, 69364, Lyon cedex 07</wicri:regionArea>
<placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
<settlement type="city">Lyon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>Université Henri Poincaré, Nancy-Université</wicri:regionArea>
<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="university">Nancy-Université</orgName>
<orgName type="university" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>LORIA, BP 239, 54506, Vandœuvre-lès-Nancy cedex</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>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Hoyrup, Mathieu" sort="Hoyrup, Mathieu" uniqKey="Hoyrup M" first="Mathieu" last="Hoyrup">Mathieu Hoyrup</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Nancy - Grand Est, Villers-lès-Nancy</wicri:regionArea>
<wicri:noRegion>Villers-lès-Nancy</wicri:noRegion>
<wicri:noRegion>Villers-lès-Nancy</wicri:noRegion>
</affiliation>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>LORIA, BP 239, 54506, Vandœuvre-lès-Nancy cedex</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>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Pechoux, Romain" sort="Pechoux, Romain" uniqKey="Pechoux R" first="Romain" last="Péchoux">Romain Péchoux</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>Université Nancy 2, Nancy-Université</wicri:regionArea>
<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="university">Nancy-Université</orgName>
<orgName type="university" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>LORIA, BP 239, 54506, Vandœuvre-lès-Nancy cedex</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>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We study polynomial time complexity of type 2 functionals. For that purpose, we introduce a first order functional stream language. We give criteria, named well-founded, on such programs relying on second order interpretation that characterize two variants of type 2 polynomial complexity including the Basic Feasible Functions (BFF). These characterizations provide a new insight on the complexity of stream programs. Finally, we adapt these results to functions over the reals, a particular case of type 2 functions, and we provide a characterization of polynomial time complexity in Recursive Analysis.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Auvergne-Rhône-Alpes</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Rhône-Alpes</li>
</region>
<settlement><li>Lyon</li>
<li>Nancy</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
<orgName><li>Nancy-Université</li>
<li>Université de Lorraine</li>
</orgName>
</list>
<tree><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Feree, Hugo" sort="Feree, Hugo" uniqKey="Feree H" first="Hugo" last="Férée">Hugo Férée</name>
</region>
<name sortKey="Feree, Hugo" sort="Feree, Hugo" uniqKey="Feree H" first="Hugo" last="Férée">Hugo Férée</name>
<name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name>
<name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name>
<name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name>
<name sortKey="Hoyrup, Mathieu" sort="Hoyrup, Mathieu" uniqKey="Hoyrup M" first="Mathieu" last="Hoyrup">Mathieu Hoyrup</name>
<name sortKey="Hoyrup, Mathieu" sort="Hoyrup, Mathieu" uniqKey="Hoyrup M" first="Mathieu" last="Hoyrup">Mathieu Hoyrup</name>
<name sortKey="Hoyrup, Mathieu" sort="Hoyrup, Mathieu" uniqKey="Hoyrup M" first="Mathieu" last="Hoyrup">Mathieu Hoyrup</name>
<name sortKey="Pechoux, Romain" sort="Pechoux, Romain" uniqKey="Pechoux R" first="Romain" last="Péchoux">Romain Péchoux</name>
<name sortKey="Pechoux, Romain" sort="Pechoux, Romain" uniqKey="Pechoux R" first="Romain" last="Péchoux">Romain Péchoux</name>
<name sortKey="Pechoux, Romain" sort="Pechoux, Romain" uniqKey="Pechoux R" first="Romain" last="Péchoux">Romain Péchoux</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003064 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003064 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:5EEB206F6262CC894E2DA85530DB2F5A417619C5
   |texte=   Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity

Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity

Source :

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri