Publikation:

Generic separations and leaf languages

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2003

Autor:innen

Galota, Matthias
Vollmer, Heribert

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

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

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690GALOTA, 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.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#" > 
  <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

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Ja
Diese Publikation teilen