## Generic separations and leaf languages

No Thumbnail Available
##### Files
There are no files associated with this item.
2003
##### Authors
Galota, Matthias
Vollmer, Heribert
Journal article
Published
##### Published in
Mathematical Logic Quarterly ; 49 (2003), 4. - pp. 353-362. - ISSN 0942-5616. - eISSN 1521-3870
##### Abstract
In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P (polynomial time) and PSPACE (polynomial space). It was shown that the separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense of Blum and Impagliazzo. We obtain several consequences of this result, regarding, e. g., universal oracles, simultaneous separations and type‐2 complexity.
##### Subject (DDC)
004 Computer Science
##### Cite This
ISO 690GALOTA, Matthias, Sven KOSUB, Heribert VOLLMER, 2003. Generic separations and leaf languages. In: Mathematical Logic Quarterly. 49(4), pp. 353-362. ISSN 0942-5616. eISSN 1521-3870. Available under: doi: 10.1002/malq.200310037
BibTex
@article{Galota2003-07Gener-44943,
year={2003},
doi={10.1002/malq.200310037},
title={Generic separations and leaf languages},
number={4},
volume={49},
issn={0942-5616},
journal={Mathematical Logic Quarterly},
pages={353--362},
author={Galota, Matthias and Kosub, Sven and Vollmer, Heribert}
}

RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<dcterms:issued>2003-07</dcterms:issued>
<dc:creator>Kosub, Sven</dc:creator>
<dcterms:abstract xml:lang="eng">In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P (polynomial time) and PSPACE (polynomial space). It was shown that the separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense of Blum and Impagliazzo. We obtain several consequences of this result, regarding, e. g., universal oracles, simultaneous separations and type‐2 complexity.</dcterms:abstract>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44943"/>
<dc:language>eng</dc:language>
<dc:contributor>Kosub, Sven</dc:contributor>
<dcterms:title>Generic separations and leaf languages</dcterms:title>
<dc:contributor>Galota, Matthias</dc:contributor>
<dc:contributor>Vollmer, Heribert</dc:contributor>
<dc:creator>Vollmer, Heribert</dc:creator>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-08T13:36:20Z</dcterms:available>
<dc:creator>Galota, Matthias</dc:creator>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-08T13:36:20Z</dc:date>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
</rdf:Description>
</rdf:RDF>

No
Yes