Publikation: Generic separations and leaf languages
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2003
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
Mathematical Logic Quarterly. 2003, 49(4), pp. 353-362. ISSN 0942-5616. eISSN 1521-3870. Available under: doi: 10.1002/malq.200310037
Zusammenfassung
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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
GALOTA, Matthias, Sven KOSUB, Heribert VOLLMER, 2003. Generic separations and leaf languages. In: Mathematical Logic Quarterly. 2003, 49(4), pp. 353-362. ISSN 0942-5616. eISSN 1521-3870. Available under: doi: 10.1002/malq.200310037BibTex
@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#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/44943"> <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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Ja