A characterization of alternating log time by ramified recurrence
Identifieur interne : 00A640 ( Main/Merge ); précédent : 00A639; suivant : 00A641A characterization of alternating log time by ramified recurrence
Auteurs : D. Leivant [États-Unis] ; J.-Y. Marion [France]Source :
- Theoretical computer science [ 0304-3975 ] ; 2000.
Descripteurs français
- Pascal (Inist)
- Wicri :
- topic : Simulation.
English descriptors
- KwdEn :
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 UE*-uniform variant of NC1 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.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000A51
- to stream PascalFrancis, to step Curation: 000031
- to stream PascalFrancis, to step Checkpoint: 000A34
Links to Exploration step
Pascal:00-0264081Le 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 wicri:level="1"><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><country>États-Unis</country><wicri:noRegion>Bloomington, IN 47405</wicri:noRegion></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 wicri:level="4"><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><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><orgName type="university">Université Nancy 2</orgName></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><idno type="wicri:Area/PascalFrancis/Curation">000031</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000A34</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A34</idno><idno type="wicri:doubleKey">0304-3975:2000:Leivant D:a:characterization:of</idno><idno type="wicri:Area/Main/Merge">00A640</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 wicri:level="1"><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><country>États-Unis</country><wicri:noRegion>Bloomington, IN 47405</wicri:noRegion></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 wicri:level="4"><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><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><orgName type="university">Université Nancy 2</orgName></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><keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Simulation</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><affiliations><list><country><li>France</li><li>États-Unis</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Vandœuvre-lès-Nancy</li></settlement><orgName><li>Université Nancy 2</li></orgName></list><tree><country name="États-Unis"><noRegion><name sortKey="Leivant, D" sort="Leivant, D" uniqKey="Leivant D" first="D." last="Leivant">D. Leivant</name></noRegion></country><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 00A640 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00A640 | 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:00-0264081
|texte= A characterization of alternating log time by ramified recurrence
}}
| This area was generated with Dilib version V0.6.33. |  |