Publikation: Boolean NP-Partitions and Projective Closure
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
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
CALUDE, Christian S., ed., Michael J. DINNEEN, ed., Vincent VAJNOVSZKI, ed.. Discrete Mathematics and Theoretical Computer Science : 4th International Conference, DMTCS 2003, Proceedings. Berlin: Springer, 2003, pp. 225-236. Lecture Notes in Computer Science. 2731. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-40505-4. Available under: doi: 10.1007/3-540-45066-1_18
Zusammenfassung
When studying complexity classes of partitions we often face the situation that different partition classes have the same component classes. The projective closures are the largest classes among these with respect to set inclusion. In this paper we investigate projective closures of classes of boolean NP-partitions, i.e., partitions with components that have complexity upper-bounds in the boolean hierarchy over NP. We prove that the projective closures of these classes are represented by finite labeled posets. We give algorithms for calculating these posets and related problems. As a consequence we obtain representations of the set classes NP(m) ∩ coNP(m) by means of finite labeled posets.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
International Conference on Discrete Mathematics and Theoretical Computer Science, 7. Juli 2003 - 12. Juli 2003, Dijon, France
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
KOSUB, Sven, 2003. Boolean NP-Partitions and Projective Closure. International Conference on Discrete Mathematics and Theoretical Computer Science. Dijon, France, 7. Juli 2003 - 12. Juli 2003. In: CALUDE, Christian S., ed., Michael J. DINNEEN, ed., Vincent VAJNOVSZKI, ed.. Discrete Mathematics and Theoretical Computer Science : 4th International Conference, DMTCS 2003, Proceedings. Berlin: Springer, 2003, pp. 225-236. Lecture Notes in Computer Science. 2731. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-40505-4. Available under: doi: 10.1007/3-540-45066-1_18BibTex
@inproceedings{Kosub2003-06-18Boole-44986, year={2003}, doi={10.1007/3-540-45066-1_18}, title={Boolean NP-Partitions and Projective Closure}, number={2731}, isbn={978-3-540-40505-4}, issn={0302-9743}, publisher={Springer}, address={Berlin}, series={Lecture Notes in Computer Science}, booktitle={Discrete Mathematics and Theoretical Computer Science : 4th International Conference, DMTCS 2003, Proceedings}, pages={225--236}, editor={Calude, Christian S. and Dinneen, Michael J. and Vajnovszki, Vincent}, author={Kosub, Sven} }
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/44986"> <dcterms:title>Boolean NP-Partitions and Projective Closure</dcterms:title> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dspace:isPartOfCollection 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-12T11:59:37Z</dcterms:available> <dcterms:abstract xml:lang="eng">When studying complexity classes of partitions we often face the situation that different partition classes have the same component classes. The projective closures are the largest classes among these with respect to set inclusion. In this paper we investigate projective closures of classes of boolean NP-partitions, i.e., partitions with components that have complexity upper-bounds in the boolean hierarchy over NP. We prove that the projective closures of these classes are represented by finite labeled posets. We give algorithms for calculating these posets and related problems. As a consequence we obtain representations of the set classes NP(m) ∩ coNP(m) by means of finite labeled posets.</dcterms:abstract> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-12T11:59:37Z</dc:date> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44986"/> <dc:contributor>Kosub, Sven</dc:contributor> <dc:creator>Kosub, Sven</dc:creator> <dc:language>eng</dc:language> <dcterms:issued>2003-06-18</dcterms:issued> <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