Separating complexity classes related to bounded alternating ω-branching programs
Identifieur interne : 001259 ( Istex/Corpus ); précédent : 001258; suivant : 001260Separating complexity classes related to bounded alternating ω-branching programs
Auteurs : C. Meinel ; S. WaackSource :
- Mathematical systems theory [ 0025-5661 ] ; 1995-01-01.
Abstract
Abstract: We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of Ω-branching programs, ω: ℕ → ℝ, a semiring homomorphism, that generalizes ordinary branching programs, Ω-branching programs [M2] andMOD p-branching programs [DKMW]. Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating ω-branching programs we are able to separate the corresponding complexity classesNℒ ba ,co-Nℒ ba ⊕ℒ ba , andMOD p -ℒ ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.
Url:
DOI: 10.1007/BF01294594
Links to Exploration step
ISTEX:7C5613666DF015686B55A8B2DCA0975379BC09BELe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Separating complexity classes related to bounded alternating ω-branching programs</title><author><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">C. Meinel</name><affiliation><mods:affiliation>FB IV-Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation></affiliation></author><author><name sortKey="Waack, S" sort="Waack, S" uniqKey="Waack S" first="S." last="Waack">S. Waack</name><affiliation><mods:affiliation>Institut für Numerisch und Angewandte Mathematik, Georg-August-Universität Göttingen, D-37083, Göttingen, Germany</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7C5613666DF015686B55A8B2DCA0975379BC09BE</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1007/BF01294594</idno><idno type="url">https://api.istex.fr/document/7C5613666DF015686B55A8B2DCA0975379BC09BE/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001259</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001259</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Separating complexity classes related to bounded alternating ω-branching programs</title><author><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">C. Meinel</name><affiliation><mods:affiliation>FB IV-Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation></affiliation></author><author><name sortKey="Waack, S" sort="Waack, S" uniqKey="Waack S" first="S." last="Waack">S. Waack</name><affiliation><mods:affiliation>Institut für Numerisch und Angewandte Mathematik, Georg-August-Universität Göttingen, D-37083, Göttingen, Germany</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Mathematical systems theory</title><title level="j" type="abbrev">Math. Systems Theory</title><idno type="ISSN">0025-5661</idno><idno type="eISSN">1433-0490</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>New York</pubPlace><date type="published" when="1995-01-01">1995-01-01</date><biblScope unit="volume">28</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="21">21</biblScope><biblScope unit="page" to="39">39</biblScope></imprint><idno type="ISSN">0025-5661</idno></series><idno type="istex">7C5613666DF015686B55A8B2DCA0975379BC09BE</idno><idno type="DOI">10.1007/BF01294594</idno><idno type="ArticleID">BF01294594</idno><idno type="ArticleID">Art3</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0025-5661</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of Ω-branching programs, ω: ℕ → ℝ, a semiring homomorphism, that generalizes ordinary branching programs, Ω-branching programs [M2] andMOD p-branching programs [DKMW]. Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating ω-branching programs we are able to separate the corresponding complexity classesNℒ ba ,co-Nℒ ba ⊕ℒ ba , andMOD p -ℒ ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>C. Meinel</name><affiliations><json:string>FB IV-Informatik, Universität Trier, D-54286, Trier, Germany</json:string></affiliations></json:item><json:item><name>S. Waack</name><affiliations><json:string>Institut für Numerisch und Angewandte Mathematik, Georg-August-Universität Göttingen, D-37083, Göttingen, Germany</json:string></affiliations></json:item></author><articleId><json:string>BF01294594</json:string><json:string>Art3</json:string></articleId><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of Ω-branching programs, ω: ℕ → ℝ, a semiring homomorphism, that generalizes ordinary branching programs, Ω-branching programs [M2] andMOD p-branching programs [DKMW]. Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating ω-branching programs we are able to separate the corresponding complexity classesNℒ ba ,co-Nℒ ba ⊕ℒ ba , andMOD p -ℒ ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.</abstract><qualityIndicators><score>6.332</score><pdfVersion>1.3</pdfVersion><pdfPageSize>446.28 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>747</abstractCharCount><pdfWordCount>6054</pdfWordCount><pdfCharCount>30022</pdfCharCount><pdfPageCount>19</pdfPageCount><abstractWordCount>111</abstractWordCount></qualityIndicators><title>Separating complexity classes related to bounded alternating ω-branching programs</title><refBibs><json:item><author><json:item><name>N Alon</name></json:item><json:item><name>W </name></json:item></author><host><volume>37</volume><pages><last>129</last><first>118</first></pages><author></author><title>J.. Comput. System Sci</title><publicationDate>1988</publicationDate></host><title>Maass: Meanders, Ramsey Theory and Lower Bounds</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>G Buntrock</name></json:item><json:item><name>C Damm</name></json:item><json:item><name>U Hertrampf</name></json:item><json:item><name> Ch</name></json:item><json:item><name> Meinel</name></json:item></author><host><pages><last>371</last><first>360</first></pages><author></author><title>Structure and Importance of Logspace- MOD-classes, Proc. STACS '91 Also in Math. Systems Theory</title><publicationDate>1992</publicationDate></host><publicationDate>1992</publicationDate></json:item><json:item><author><json:item><name>D Datum</name></json:item><json:item><name>M Krause</name></json:item><json:item><name> Ch</name></json:item><json:item><name>S Meinel</name></json:item><json:item><name> Waack Humboldt-University</name></json:item><json:item><name>M Berlin</name></json:item><json:item><name> Krause</name></json:item><json:item><name>@ Separating</name></json:item><json:item><name>Al W From S Eo-Jvs162</name></json:item><json:item><name>Oblivious Turing</name></json:item><json:item><name>M Krause</name></json:item><json:item><name> Ch</name></json:item><json:item><name>S Meinel</name></json:item><json:item><name> Waack</name></json:item></author><host><pages><last>391</last><first>385</first></pages><author></author><title>Machines of Linear Access Time, Proe. MFCS '90 Proe. MFCS "88 Separating Complexity Classes Related to Certain Input Oblivious Logarithmic Space Bounded Turing Machines, Proc. 4th IEEE Structure in Complexity Theory</title><publicationDate>1959</publicationDate></host><title>Separating Restricted MODp-Branching Program Classes Separating the Eraser Turing Machine Classes See, JVSee, co-sV'L~ae and ~e</title><publicationDate>1959</publicationDate></json:item><json:item><author><json:item><name> Ch</name></json:item></author><host><pages><last>90</last><first>81</first></pages><author></author><title>Proc. STACS '88 Ch. Meinel: Modified Branching Programs and Their Computational Power</title><publicationDate>1989</publicationDate></host><title>Polynomial Size f~-Branching Programs and Their Computational Power</title><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name> Ch</name></json:item><json:item><name>S Meinel</name></json:item><json:item><name> Waack</name></json:item></author><host><pages><last>345</last><first>337</first></pages><author></author><title>Proc. MFCS "91</title></host><title>Upper and Lower Bounds for Certain Graph-Accessibility- Problems on Bounded Alternating Branching Programs</title></json:item><json:item><author><json:item><name>P Pudlhk</name></json:item><json:item><name>S,~ </name></json:item></author><host><pages><last>192</last><first>177</first></pages><author></author><title>Space Complexity of Computations Savitch: Relations Between Nondeterministic and Deterministic Tape Complexities</title><publicationDate>1970</publicationDate></host><publicationDate>1970</publicationDate></json:item><json:item><author><json:item><name> Wegener</name></json:item></author><host><volume>35</volume><pages><last>471</last><first>461</first></pages><issue>2</issue><author></author><title>J. Assoc. Comput. Mach</title><publicationDate>1988</publicationDate></host><title>The Complexity of Branching Programs and Decision Trees for Clique Functions</title><publicationDate>1988</publicationDate></json:item></refBibs><genre><json:string>research-article</json:string></genre><host><volume>28</volume><pages><last>39</last><first>21</first></pages><issn><json:string>0025-5661</json:string></issn><issue>1</issue><subject><json:item><value>Theory of Computation</value></json:item><json:item><value>Computational Mathematics and Numerical Analysis</value></json:item></subject><journalId><json:string>224</json:string></journalId><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><eissn><json:string>1433-0490</json:string></eissn><title>Mathematical systems theory</title><publicationDate>1995</publicationDate><copyrightDate>1995</copyrightDate></host><publicationDate>1995</publicationDate><copyrightDate>1995</copyrightDate><doi><json:string>10.1007/BF01294594</json:string></doi><id>7C5613666DF015686B55A8B2DCA0975379BC09BE</id><score>0.47465461</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/7C5613666DF015686B55A8B2DCA0975379BC09BE/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/7C5613666DF015686B55A8B2DCA0975379BC09BE/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/7C5613666DF015686B55A8B2DCA0975379BC09BE/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Separating complexity classes related to bounded alternating ω-branching programs</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer-Verlag</publisher><pubPlace>New York</pubPlace><availability><p>Springer-Verlag New York Inc., 1995</p></availability><date>1991-09-18</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Separating complexity classes related to bounded alternating ω-branching programs</title><author xml:id="author-1"><persName><forename type="first">C.</forename><surname>Meinel</surname></persName><affiliation>FB IV-Informatik, Universität Trier, D-54286, Trier, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">S.</forename><surname>Waack</surname></persName><affiliation>Institut für Numerisch und Angewandte Mathematik, Georg-August-Universität Göttingen, D-37083, Göttingen, Germany</affiliation></author></analytic><monogr><title level="j">Mathematical systems theory</title><title level="j" type="abbrev">Math. Systems Theory</title><idno type="journal-ID">224</idno><idno type="pISSN">0025-5661</idno><idno type="eISSN">1433-0490</idno><idno type="issue-article-count">5</idno><idno type="volume-issue-count">6</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>New York</pubPlace><date type="published" when="1995-01-01"></date><biblScope unit="volume">28</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="21">21</biblScope><biblScope unit="page" to="39">39</biblScope></imprint></monogr><idno type="istex">7C5613666DF015686B55A8B2DCA0975379BC09BE</idno><idno type="DOI">10.1007/BF01294594</idno><idno type="ArticleID">BF01294594</idno><idno type="ArticleID">Art3</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1991-09-18</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of Ω-branching programs, ω: ℕ → ℝ, a semiring homomorphism, that generalizes ordinary branching programs, Ω-branching programs [M2] andMOD p-branching programs [DKMW]. Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating ω-branching programs we are able to separate the corresponding complexity classesNℒ ba ,co-Nℒ ba ⊕ℒ ba , andMOD p -ℒ ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.</p></abstract><textClass><keywords scheme="Journal Subject"><list><head>Computer Science</head><item><term>Theory of Computation</term></item><item><term>Computational Mathematics and Numerical Analysis</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1991-09-18">Created</change><change when="1995-01-01">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/7C5613666DF015686B55A8B2DCA0975379BC09BE/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer-Verlag</PublisherName><PublisherLocation>New York</PublisherLocation></PublisherInfo><Journal><JournalInfo JournalProductType="ArchiveJournal" NumberingStyle="Unnumbered"><JournalID>224</JournalID><JournalPrintISSN>0025-5661</JournalPrintISSN><JournalElectronicISSN>1433-0490</JournalElectronicISSN><JournalTitle>Mathematical systems theory</JournalTitle><JournalAbbreviatedTitle>Math. Systems Theory</JournalAbbreviatedTitle><JournalSubjectGroup><JournalSubject Type="Primary">Computer Science</JournalSubject><JournalSubject Type="Secondary">Theory of Computation</JournalSubject><JournalSubject Type="Secondary">Computational Mathematics and Numerical Analysis</JournalSubject></JournalSubjectGroup></JournalInfo><Volume><VolumeInfo VolumeType="Regular" TocLevels="0"><VolumeIDStart>28</VolumeIDStart><VolumeIDEnd>28</VolumeIDEnd><VolumeIssueCount>6</VolumeIssueCount></VolumeInfo><Issue IssueType="Regular"><IssueInfo TocLevels="0"><IssueIDStart>1</IssueIDStart><IssueIDEnd>1</IssueIDEnd><IssueArticleCount>5</IssueArticleCount><IssueHistory><CoverDate><DateString>January/February 1995</DateString><Year>1995</Year><Month>1</Month></CoverDate></IssueHistory><IssueCopyright><CopyrightHolderName>Springer-Verlag New York Inc.</CopyrightHolderName><CopyrightYear>1995</CopyrightYear></IssueCopyright></IssueInfo><Article ID="Art3"><ArticleInfo Language="En" ArticleType="OriginalPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ArticleID>BF01294594</ArticleID><ArticleDOI>10.1007/BF01294594</ArticleDOI><ArticleSequenceNumber>3</ArticleSequenceNumber><ArticleTitle Language="En">Separating complexity classes related to bounded alternating ω-branching programs</ArticleTitle><ArticleFirstPage>21</ArticleFirstPage><ArticleLastPage>39</ArticleLastPage><ArticleHistory><RegistrationDate><Year>2005</Year><Month>2</Month><Day>24</Day></RegistrationDate><Received><Year>1991</Year><Month>9</Month><Day>18</Day></Received><Accepted><Year>1992</Year><Month>10</Month><Day>5</Day></Accepted></ArticleHistory><ArticleCopyright><CopyrightHolderName>Springer-Verlag New York Inc.</CopyrightHolderName><CopyrightYear>1995</CopyrightYear></ArticleCopyright><ArticleGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ArticleGrants><ArticleContext><JournalID>224</JournalID><VolumeIDStart>28</VolumeIDStart><VolumeIDEnd>28</VolumeIDEnd><IssueIDStart>1</IssueIDStart><IssueIDEnd>1</IssueIDEnd></ArticleContext></ArticleInfo><ArticleHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Meinel</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>S.</GivenName><FamilyName>Waack</FamilyName></AuthorName></Author><Affiliation ID="Aff1"><OrgDivision>FB IV-Informatik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postcode>D-54286</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Institut für Numerisch und Angewandte Mathematik</OrgDivision><OrgName>Georg-August-Universität Göttingen</OrgName><OrgAddress><Postcode>D-37083</Postcode><City>Göttingen</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of Ω-branching programs, ω: ℕ → ℝ, a semiring homomorphism, that generalizes ordinary branching programs, Ω-branching programs [M2] and<Emphasis Type="Italic">MOD</Emphasis><Subscript>p</Subscript>-branching programs [DKMW].</Para><Para>Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating ω-branching programs we are able to separate the corresponding complexity classes<Emphasis FontCategory="NonProportional">N</Emphasis>ℒ<Subscript><Emphasis Type="Italic">ba</Emphasis></Subscript>,<Emphasis Type="Italic">co</Emphasis>-<Emphasis FontCategory="NonProportional">N</Emphasis>ℒ<Subscript><Emphasis Type="Italic">ba</Emphasis></Subscript>⊕ℒ<Subscript><Emphasis Type="Italic">ba</Emphasis></Subscript>, and<Emphasis Type="Italic">MOD</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-ℒ<Subscript><Emphasis Type="Italic">ba</Emphasis></Subscript>,<Emphasis Type="Italic">p</Emphasis> prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.</Para></Abstract></ArticleHeader><NoBody></NoBody></Article></Issue></Volume></Journal></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Separating complexity classes related to bounded alternating ω-branching programs</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Separating complexity classes related to bounded alternating ω-branching programs</title></titleInfo><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Meinel</namePart><affiliation>FB IV-Informatik, Universität Trier, D-54286, Trier, Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">S.</namePart><namePart type="family">Waack</namePart><affiliation>Institut für Numerisch und Angewandte Mathematik, Georg-August-Universität Göttingen, D-37083, Göttingen, Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer-Verlag</publisher><place><placeTerm type="text">New York</placeTerm></place><dateCreated encoding="w3cdtf">1991-09-18</dateCreated><dateIssued encoding="w3cdtf">1995-01-01</dateIssued><copyrightDate encoding="w3cdtf">1995</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of Ω-branching programs, ω: ℕ → ℝ, a semiring homomorphism, that generalizes ordinary branching programs, Ω-branching programs [M2] andMOD p-branching programs [DKMW]. Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating ω-branching programs we are able to separate the corresponding complexity classesNℒ ba ,co-Nℒ ba ⊕ℒ ba , andMOD p -ℒ ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.</abstract><relatedItem type="host"><titleInfo><title>Mathematical systems theory</title></titleInfo><titleInfo type="abbreviated"><title>Math. Systems Theory</title></titleInfo><genre type="journal" displayLabel="Archive Journal"></genre><originInfo><dateIssued encoding="w3cdtf">1995-01-01</dateIssued><copyrightDate encoding="w3cdtf">1995</copyrightDate></originInfo><subject><genre>Computer Science</genre><topic>Theory of Computation</topic><topic>Computational Mathematics and Numerical Analysis</topic></subject><identifier type="ISSN">0025-5661</identifier><identifier type="eISSN">1433-0490</identifier><identifier type="JournalID">224</identifier><identifier type="IssueArticleCount">5</identifier><identifier type="VolumeIssueCount">6</identifier><part><date>1995</date><detail type="volume"><number>28</number><caption>vol.</caption></detail><detail type="issue"><number>1</number><caption>no.</caption></detail><extent unit="pages"><start>21</start><end>39</end></extent></part><recordInfo><recordOrigin>Springer-Verlag New York Inc., 1995</recordOrigin></recordInfo></relatedItem><identifier type="istex">7C5613666DF015686B55A8B2DCA0975379BC09BE</identifier><identifier type="DOI">10.1007/BF01294594</identifier><identifier type="ArticleID">BF01294594</identifier><identifier type="ArticleID">Art3</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag New York Inc., 1995</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag New York Inc., 1995</recordOrigin></recordInfo></mods></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001259 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001259 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:7C5613666DF015686B55A8B2DCA0975379BC09BE
|texte= Separating complexity classes related to bounded alternating ω-branching programs
}}
| This area was generated with Dilib version V0.6.31. |  |