InforLorV4, PascalFrancis, Corpus, bibRecord, 000472

Implicit complexity over an arbitrary structure : Quantifier alternations

Identifieur interne : 000472 ( PascalFrancis/Corpus ); précédent : 000471; suivant : 000473

Implicit complexity over an arbitrary structure : Quantifier alternations

Auteurs : Olivier Bournez ; Felipe Cucker ; Paulin Jacobe De Naurois ; Jean-Yves Marion

Source :

Information and computation : (Print) [ 0890-5401 ] ; 2006.

RBID : Pascal:06-0124363

Descripteurs français

Pascal (Inist)
- Quantificateur, Classe complexité, Minimisation, Temps polynomial, Informatique théorique, Modèle calcul, Hiérarchie polynomiale, Récursion, Structure arbitraire, Calcul BSS, Compléxité implicite.

English descriptors

KwdEn :
- Arbitrary structure, BSS computation, Complexity class, Computer theory, Implicit complexity, Minimization, Polynomial time, Quantifier.

Abstract

We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0890-5401`
A02	`01`			`@0 INFCEC`
A03		`1`		`@0 Inf. comput. : (Print)`
A05				`@2 204`
A06				`@2 2`
A08	`01`	`1`	`ENG`	`@1 Implicit complexity over an arbitrary structure : Quantifier alternations`
A11	`01`	`1`		`@1 BOURNEZ (Olivier)`
A11	`02`	`1`		`@1 CUCKER (Felipe)`
A11	`03`	`1`		`@1 JACOBE DE NAUROIS (Paulin)`
A11	`04`	`1`		`@1 MARION (Jean-Yves)`
A14	`01`			`@1 LORIA, 615 rue du Jardin Botanique, BP 101 @2 54602 Villers-lès-Nancy @3 FRA @Z 1 aut. @Z 3 aut. @Z 4 aut.`
A14	`02`			`@1 Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue @2 Kowloon @3 HKG @Z 2 aut.`
A20				`@1 210-230`
A21				`@1 2006`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 8341 @5 354000115142550020`
A44				`@0 0000 @1 © 2006 INIST-CNRS. All rights reserved.`
A45				`@0 24 ref.`
A47	`01`	`1`		`@0 06-0124363`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 Information and computation : (Print)`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	@0 We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.
C02	`01`	`X`		`@0 001D02A05`
C03	`01`	`X`	`FRE`	`@0 Quantificateur @5 18`
C03	`01`	`X`	`ENG`	`@0 Quantifier @5 18`
C03	`01`	`X`	`SPA`	`@0 Cuantificador @5 18`
C03	`02`	`X`	`FRE`	`@0 Classe complexité @5 20`
C03	`02`	`X`	`ENG`	`@0 Complexity class @5 20`
C03	`02`	`X`	`SPA`	`@0 Clase complejidad @5 20`
C03	`03`	`X`	`FRE`	`@0 Minimisation @5 22`
C03	`03`	`X`	`ENG`	`@0 Minimization @5 22`
C03	`03`	`X`	`SPA`	`@0 Minimización @5 22`
C03	`04`	`X`	`FRE`	`@0 Temps polynomial @5 23`
C03	`04`	`X`	`ENG`	`@0 Polynomial time @5 23`
C03	`04`	`X`	`SPA`	`@0 Tiempo polinomial @5 23`
C03	`05`	`X`	`FRE`	`@0 Informatique théorique @5 25`
C03	`05`	`X`	`ENG`	`@0 Computer theory @5 25`
C03	`05`	`X`	`SPA`	`@0 Informática teórica @5 25`
C03	`06`	`X`	`FRE`	`@0 Modèle calcul @4 INC @5 72`
C03	`07`	`X`	`FRE`	`@0 Hiérarchie polynomiale @4 INC @5 73`
C03	`08`	`X`	`FRE`	`@0 Récursion @4 INC @5 75`
C03	`09`	`X`	`FRE`	`@0 Structure arbitraire @4 CD @5 96`
C03	`09`	`X`	`ENG`	`@0 Arbitrary structure @4 CD @5 96`
C03	`10`	`X`	`FRE`	`@0 Calcul BSS @4 CD @5 97`
C03	`10`	`X`	`ENG`	`@0 BSS computation @4 CD @5 97`
C03	`11`	`X`	`FRE`	`@0 Compléxité implicite @4 CD @5 98`
C03	`11`	`X`	`ENG`	`@0 Implicit complexity @4 CD @5 98`
N21				`@1 072`

Format Inist (serveur)

NO :	PASCAL 06-0124363 INIST
ET :	Implicit complexity over an arbitrary structure : Quantifier alternations
AU :	BOURNEZ (Olivier); CUCKER (Felipe); JACOBE DE NAUROIS (Paulin); MARION (Jean-Yves)
AF :	LORIA, 615 rue du Jardin Botanique, BP 101/54602 Villers-lès-Nancy/France (1 aut., 3 aut., 4 aut.); Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue/Kowloon/Hong-Kong (2 aut.)
DT :	Publication en série; Niveau analytique
SO :	Information and computation : (Print); ISSN 0890-5401; Coden INFCEC; Etats-Unis; Da. 2006; Vol. 204; No. 2; Pp. 210-230; Bibl. 24 ref.
LA :	Anglais
EA :	We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.
CC :	001D02A05
FD :	Quantificateur; Classe complexité; Minimisation; Temps polynomial; Informatique théorique; Modèle calcul; Hiérarchie polynomiale; Récursion; Structure arbitraire; Calcul BSS; Compléxité implicite
ED :	Quantifier; Complexity class; Minimization; Polynomial time; Computer theory; Arbitrary structure; BSS computation; Implicit complexity
SD :	Cuantificador; Clase complejidad; Minimización; Tiempo polinomial; Informática teórica
LO :	INIST-8341.354000115142550020
ID :	06-0124363

Links to Exploration step

Pascal:06-0124363

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Implicit complexity over an arbitrary structure : Quantifier alternations</title>
<author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA, 615 rue du Jardin Botanique, BP 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Cucker, Felipe" sort="Cucker, Felipe" uniqKey="Cucker F" first="Felipe" last="Cucker">Felipe Cucker</name>
<affiliation><inist:fA14 i1="02"><s1>Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue</s1>
<s2>Kowloon</s2>
<s3>HKG</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Jacobe De Naurois, Paulin" sort="Jacobe De Naurois, Paulin" uniqKey="Jacobe De Naurois P" first="Paulin" last="Jacobe De Naurois">Paulin Jacobe De Naurois</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA, 615 rue du Jardin Botanique, BP 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA, 615 rue du Jardin Botanique, BP 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">06-0124363</idno>
<date when="2006">2006</date>
<idno type="stanalyst">PASCAL 06-0124363 INIST</idno>
<idno type="RBID">Pascal:06-0124363</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000472</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Implicit complexity over an arbitrary structure : Quantifier alternations</title>
<author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA, 615 rue du Jardin Botanique, BP 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Cucker, Felipe" sort="Cucker, Felipe" uniqKey="Cucker F" first="Felipe" last="Cucker">Felipe Cucker</name>
<affiliation><inist:fA14 i1="02"><s1>Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue</s1>
<s2>Kowloon</s2>
<s3>HKG</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Jacobe De Naurois, Paulin" sort="Jacobe De Naurois, Paulin" uniqKey="Jacobe De Naurois P" first="Paulin" last="Jacobe De Naurois">Paulin Jacobe De Naurois</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA, 615 rue du Jardin Botanique, BP 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA, 615 rue du Jardin Botanique, BP 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</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="2006">2006</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>Arbitrary structure</term>
<term>BSS computation</term>
<term>Complexity class</term>
<term>Computer theory</term>
<term>Implicit complexity</term>
<term>Minimization</term>
<term>Polynomial time</term>
<term>Quantifier</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Quantificateur</term>
<term>Classe complexité</term>
<term>Minimisation</term>
<term>Temps polynomial</term>
<term>Informatique théorique</term>
<term>Modèle calcul</term>
<term>Hiérarchie polynomiale</term>
<term>Récursion</term>
<term>Structure arbitraire</term>
<term>Calcul BSS</term>
<term>Compléxité implicite</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0890-5401</s0>
</fA01>
<fA02 i1="01"><s0>INFCEC</s0>
</fA02>
<fA03 i2="1"><s0>Inf. comput. : (Print)</s0>
</fA03>
<fA05><s2>204</s2>
</fA05>
<fA06><s2>2</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>Implicit complexity over an arbitrary structure : Quantifier alternations</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>BOURNEZ (Olivier)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>CUCKER (Felipe)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>JACOBE DE NAUROIS (Paulin)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>MARION (Jean-Yves)</s1>
</fA11>
<fA14 i1="01"><s1>LORIA, 615 rue du Jardin Botanique, BP 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue</s1>
<s2>Kowloon</s2>
<s3>HKG</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA20><s1>210-230</s1>
</fA20>
<fA21><s1>2006</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>8341</s2>
<s5>354000115142550020</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2006 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>24 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>06-0124363</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Information and computation : (Print)</s0>
</fA64>
<fA66 i1="01"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Quantificateur</s0>
<s5>18</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Quantifier</s0>
<s5>18</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Cuantificador</s0>
<s5>18</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Classe complexité</s0>
<s5>20</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Complexity class</s0>
<s5>20</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Clase complejidad</s0>
<s5>20</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Minimisation</s0>
<s5>22</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Minimization</s0>
<s5>22</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Minimización</s0>
<s5>22</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Temps polynomial</s0>
<s5>23</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Polynomial time</s0>
<s5>23</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Tiempo polinomial</s0>
<s5>23</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Informatique théorique</s0>
<s5>25</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Computer theory</s0>
<s5>25</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Informática teórica</s0>
<s5>25</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Modèle calcul</s0>
<s4>INC</s4>
<s5>72</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Hiérarchie polynomiale</s0>
<s4>INC</s4>
<s5>73</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Récursion</s0>
<s4>INC</s4>
<s5>75</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Structure arbitraire</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Arbitrary structure</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE"><s0>Calcul BSS</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="10" i2="X" l="ENG"><s0>BSS computation</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="11" i2="X" l="FRE"><s0>Compléxité implicite</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03>
<fC03 i1="11" i2="X" l="ENG"><s0>Implicit complexity</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03>
<fN21><s1>072</s1>
</fN21>
</pA>
</standard>
<server><NO>PASCAL 06-0124363 INIST</NO>
<ET>Implicit complexity over an arbitrary structure : Quantifier alternations</ET>
<AU>BOURNEZ (Olivier); CUCKER (Felipe); JACOBE DE NAUROIS (Paulin); MARION (Jean-Yves)</AU>
<AF>LORIA, 615 rue du Jardin Botanique, BP 101/54602 Villers-lès-Nancy/France (1 aut., 3 aut., 4 aut.); Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue/Kowloon/Hong-Kong (2 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>Information and computation : (Print); ISSN 0890-5401; Coden INFCEC; Etats-Unis; Da. 2006; Vol. 204; No. 2; Pp. 210-230; Bibl. 24 ref.</SO>
<LA>Anglais</LA>
<EA>We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.</EA>
<CC>001D02A05</CC>
<FD>Quantificateur; Classe complexité; Minimisation; Temps polynomial; Informatique théorique; Modèle calcul; Hiérarchie polynomiale; Récursion; Structure arbitraire; Calcul BSS; Compléxité implicite</FD>
<ED>Quantifier; Complexity class; Minimization; Polynomial time; Computer theory; Arbitrary structure; BSS computation; Implicit complexity</ED>
<SD>Cuantificador; Clase complejidad; Minimización; Tiempo polinomial; Informática teórica</SD>
<LO>INIST-8341.354000115142550020</LO>
<ID>06-0124363</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

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

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000472 | SxmlIndent | more

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

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:06-0124363
   |texte=   Implicit complexity over an arbitrary structure : Quantifier alternations
}}

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

Implicit complexity over an arbitrary structure : Quantifier alternations

Implicit complexity over an arbitrary structure : Quantifier alternations

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

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