InforLorV4, PascalFrancis, Corpus, bibRecord, 000A51

A characterization of alternating log time by ramified recurrence

Identifieur interne : 000A51 ( PascalFrancis/Corpus ); précédent : 000A50; suivant : 000A52

A characterization of alternating log time by ramified recurrence

Auteurs : D. Leivant ; J.-Y. Marion

Source :

Theoretical computer science [ 0304-3975 ] ; 2000.

RBID : Pascal:00-0264081

Descripteurs français

Pascal (Inist)
- Complexité calcul, Récurrence, Arbre graphe, Substitution, Arbre binaire, Ramification, Simulation, Récursion, Récursion arbre.

English descriptors

KwdEn :
- Binary tree, Branching, Computational complexity, Recurrence, Recursion, Simulation, Substitution, Tree recursion, Tree(graph).

Abstract

We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U_E*-uniform variant of NC¹ Ruzzo, J. Comput. System Sci. 22 (1981) 365-383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.

Notice en format standard (ISO 2709)

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

A01	`01`	`1`		`@0 0304-3975`
A02	`01`			`@0 TCSCDI`
A03		`1`		`@0 Theor. comput. sci.`
A05				`@2 236`
A06				`@2 1-2`
A08	`01`	`1`	`ENG`	`@1 A characterization of alternating log time by ramified recurrence`
A09	`01`	`1`	`ENG`	`@1 Trees in Algebra and Programming`
A11	`01`	`1`		`@1 LEIVANT (D.)`
A11	`02`	`1`		`@1 MARION (J.-Y.)`
A12	`01`	`1`		`@1 DAUCHET (M.) @9 ed.`
A14	`01`			`@1 Computer Science Department, Indiana University @2 Bloomington, IN 47405 @3 USA @Z 1 aut.`
A14	`02`			`@1 Université Nancy 2, Loria, Projet Calligramme, B.P. 239, Campus Scientifique @2 54506 Vandœuvre-lès-Nancy @3 FRA @Z 2 aut.`
A15	`01`			`@1 LIFL, UFR IEEA, Université de Lille I @2 59655 Villeneuve d'Ascq @3 FRA @Z 1 aut.`
A20				`@1 193-208`
A21				`@1 2000`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 17243 @5 354000086985170050`
A44				`@0 0000 @1 © 2000 INIST-CNRS. All rights reserved.`
A45				`@0 20 ref.`
A47	`01`	`1`		`@0 00-0264081`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 Theoretical computer science`
A66	`01`			`@0 NLD`
C01	`01`		`ENG`	@0 We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U_E*-uniform variant of NC¹ Ruzzo, J. Comput. System Sci. 22 (1981) 365-383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.
C02	`01`	`X`		`@0 001D02A05`
C02	`02`	`X`		`@0 001A02B01C`
C03	`01`	`X`	`FRE`	`@0 Complexité calcul @5 01`
C03	`01`	`X`	`ENG`	`@0 Computational complexity @5 01`
C03	`01`	`X`	`SPA`	`@0 Complejidad computación @5 01`
C03	`02`	`X`	`FRE`	`@0 Récurrence @5 02`
C03	`02`	`X`	`ENG`	`@0 Recurrence @5 02`
C03	`02`	`X`	`SPA`	`@0 Recurrencia @5 02`
C03	`03`	`X`	`FRE`	`@0 Arbre graphe @5 03`
C03	`03`	`X`	`ENG`	`@0 Tree(graph) @5 03`
C03	`03`	`X`	`SPA`	`@0 Arbol grafo @5 03`
C03	`04`	`X`	`FRE`	`@0 Substitution @5 04`
C03	`04`	`X`	`ENG`	`@0 Substitution @5 04`
C03	`04`	`X`	`SPA`	`@0 Substitución @5 04`
C03	`05`	`X`	`FRE`	`@0 Arbre binaire @5 05`
C03	`05`	`X`	`ENG`	`@0 Binary tree @5 05`
C03	`05`	`X`	`SPA`	`@0 Arbol binario @5 05`
C03	`06`	`X`	`FRE`	`@0 Ramification @5 06`
C03	`06`	`X`	`ENG`	`@0 Branching @5 06`
C03	`06`	`X`	`SPA`	`@0 Ramificación @5 06`
C03	`07`	`X`	`FRE`	`@0 Simulation @5 07`
C03	`07`	`X`	`ENG`	`@0 Simulation @5 07`
C03	`07`	`X`	`SPA`	`@0 Simulación @5 07`
C03	`08`	`X`	`FRE`	`@0 Récursion @4 CD @5 96`
C03	`08`	`X`	`ENG`	`@0 Recursion @4 CD @5 96`
C03	`09`	`X`	`FRE`	`@0 Récursion arbre @4 CD @5 97`
C03	`09`	`X`	`ENG`	`@0 Tree recursion @4 CD @5 97`
N21				`@1 178`

Format Inist (serveur)

NO :	PASCAL 00-0264081 INIST
ET :	A characterization of alternating log time by ramified recurrence
AU :	LEIVANT (D.); MARION (J.-Y.); DAUCHET (M.)
AF :	Computer Science Department, Indiana University/Bloomington, IN 47405/Etats-Unis (1 aut.); Université Nancy 2, Loria, Projet Calligramme, B.P. 239, Campus Scientifique/54506 Vandœuvre-lès-Nancy/France (2 aut.); LIFL, UFR IEEA, Université de Lille I/59655 Villeneuve d'Ascq/France (1 aut.)
DT :	Publication en série; Niveau analytique
SO :	Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2000; Vol. 236; No. 1-2; Pp. 193-208; Bibl. 20 ref.
LA :	Anglais
EA :	We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U_E*-uniform variant of NC¹ Ruzzo, J. Comput. System Sci. 22 (1981) 365-383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.
CC :	001D02A05; 001A02B01C
FD :	Complexité calcul; Récurrence; Arbre graphe; Substitution; Arbre binaire; Ramification; Simulation; Récursion; Récursion arbre
ED :	Computational complexity; Recurrence; Tree(graph); Substitution; Binary tree; Branching; Simulation; Recursion; Tree recursion
SD :	Complejidad computación; Recurrencia; Arbol grafo; Substitución; Arbol binario; Ramificación; Simulación
LO :	INIST-17243.354000086985170050
ID :	00-0264081

Links to Exploration step

Pascal:00-0264081

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">A characterization of alternating log time by ramified recurrence</title>
<author><name sortKey="Leivant, D" sort="Leivant, D" uniqKey="Leivant D" first="D." last="Leivant">D. Leivant</name>
<affiliation><inist:fA14 i1="01"><s1>Computer Science Department, Indiana University</s1>
<s2>Bloomington, IN 47405</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J.-Y." last="Marion">J.-Y. Marion</name>
<affiliation><inist:fA14 i1="02"><s1>Université Nancy 2, Loria, Projet Calligramme, B.P. 239, Campus Scientifique</s1>
<s2>54506 Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">00-0264081</idno>
<date when="2000">2000</date>
<idno type="stanalyst">PASCAL 00-0264081 INIST</idno>
<idno type="RBID">Pascal:00-0264081</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A51</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">A characterization of alternating log time by ramified recurrence</title>
<author><name sortKey="Leivant, D" sort="Leivant, D" uniqKey="Leivant D" first="D." last="Leivant">D. Leivant</name>
<affiliation><inist:fA14 i1="01"><s1>Computer Science Department, Indiana University</s1>
<s2>Bloomington, IN 47405</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Marion, J Y" sort="Marion, J Y" uniqKey="Marion J" first="J.-Y." last="Marion">J.-Y. Marion</name>
<affiliation><inist:fA14 i1="02"><s1>Université Nancy 2, Loria, Projet Calligramme, B.P. 239, Campus Scientifique</s1>
<s2>54506 Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
<imprint><date when="2000">2000</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Binary tree</term>
<term>Branching</term>
<term>Computational complexity</term>
<term>Recurrence</term>
<term>Recursion</term>
<term>Simulation</term>
<term>Substitution</term>
<term>Tree recursion</term>
<term>Tree(graph)</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Complexité calcul</term>
<term>Récurrence</term>
<term>Arbre graphe</term>
<term>Substitution</term>
<term>Arbre binaire</term>
<term>Ramification</term>
<term>Simulation</term>
<term>Récursion</term>
<term>Récursion arbre</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U<sub>E*</sub>
-uniform variant of NC<sup>1</sup>
 Ruzzo, J. Comput. System Sci. 22 (1981) 365-383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0304-3975</s0>
</fA01>
<fA02 i1="01"><s0>TCSCDI</s0>
</fA02>
<fA03 i2="1"><s0>Theor. comput. sci.</s0>
</fA03>
<fA05><s2>236</s2>
</fA05>
<fA06><s2>1-2</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>A characterization of alternating log time by ramified recurrence</s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG"><s1>Trees in Algebra and Programming</s1>
</fA09>
<fA11 i1="01" i2="1"><s1>LEIVANT (D.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>MARION (J.-Y.)</s1>
</fA11>
<fA12 i1="01" i2="1"><s1>DAUCHET (M.)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01"><s1>Computer Science Department, Indiana University</s1>
<s2>Bloomington, IN 47405</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>Université Nancy 2, Loria, Projet Calligramme, B.P. 239, Campus Scientifique</s1>
<s2>54506 Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA15 i1="01"><s1>LIFL, UFR IEEA, Université de Lille I</s1>
<s2>59655 Villeneuve d'Ascq</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA15>
<fA20><s1>193-208</s1>
</fA20>
<fA21><s1>2000</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>17243</s2>
<s5>354000086985170050</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2000 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>20 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>00-0264081</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Theoretical computer science</s0>
</fA64>
<fA66 i1="01"><s0>NLD</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U<sub>E*</sub>
-uniform variant of NC<sup>1</sup>
 Ruzzo, J. Comput. System Sci. 22 (1981) 365-383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001A02B01C</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Complexité calcul</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Computational complexity</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Complejidad computación</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Récurrence</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Recurrence</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Recurrencia</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Arbre graphe</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Tree(graph)</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Arbol grafo</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Substitution</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Substitution</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Substitución</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Arbre binaire</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Binary tree</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Arbol binario</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Ramification</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Branching</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Ramificación</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Simulation</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Simulation</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Simulación</s0>
<s5>07</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Récursion</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG"><s0>Recursion</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Récursion arbre</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Tree recursion</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fN21><s1>178</s1>
</fN21>
</pA>
</standard>
<server><NO>PASCAL 00-0264081 INIST</NO>
<ET>A characterization of alternating log time by ramified recurrence</ET>
<AU>LEIVANT (D.); MARION (J.-Y.); DAUCHET (M.)</AU>
<AF>Computer Science Department, Indiana University/Bloomington, IN 47405/Etats-Unis (1 aut.); Université Nancy 2, Loria, Projet Calligramme, B.P. 239, Campus Scientifique/54506 Vandœuvre-lès-Nancy/France (2 aut.); LIFL, UFR IEEA, Université de Lille I/59655 Villeneuve d'Ascq/France (1 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2000; Vol. 236; No. 1-2; Pp. 193-208; Bibl. 20 ref.</SO>
<LA>Anglais</LA>
<EA>We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U<sub>E*</sub>
-uniform variant of NC<sup>1</sup>
 Ruzzo, J. Comput. System Sci. 22 (1981) 365-383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.</EA>
<CC>001D02A05; 001A02B01C</CC>
<FD>Complexité calcul; Récurrence; Arbre graphe; Substitution; Arbre binaire; Ramification; Simulation; Récursion; Récursion arbre</FD>
<ED>Computational complexity; Recurrence; Tree(graph); Substitution; Binary tree; Branching; Simulation; Recursion; Tree recursion</ED>
<SD>Complejidad computación; Recurrencia; Arbol grafo; Substitución; Arbol binario; Ramificación; Simulación</SD>
<LO>INIST-17243.354000086985170050</LO>
<ID>00-0264081</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 000A51 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000A51 | 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:00-0264081
   |texte=   A characterization of alternating log time by ramified recurrence
}}

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

A characterization of alternating log time by ramified recurrence

A characterization of alternating log time by ramified recurrence

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