Publikation: Koepke Machines and Satisfiability for Infinitary Propositional Languages
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2017
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
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
KARI, Jarkko, ed. and others. Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings. Cham: Springer, 2017, pp. 187-197. Lecture Notes in Computer Science. 10307. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-58740-0. Available under: doi: 10.1007/978-3-319-58741-7_19
Zusammenfassung
We consider complexity theory for Koepke machines, also known as Ordinal Turing Machines (OTMs), and define infinitary complexity classes ∞-P and ∞-NP and the OTM analogue of the satisfiability problem, denoted by ∞-SAT. We show that ∞-SAT is in ∞-NP and ∞-NP-hard (i.e., the problem is ∞-NP-complete), but not OTM decidable.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
510 Mathematik
Schlagwörter
Konferenz
13th Conference on Computability in Europe, CiE 2017, 12. Juni 2017 - 16. Juni 2017, Turku, Finland
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
CARL, Merlin, Benedikt LÖWE, Benjamin G. RIN, 2017. Koepke Machines and Satisfiability for Infinitary Propositional Languages. 13th Conference on Computability in Europe, CiE 2017. Turku, Finland, 12. Juni 2017 - 16. Juni 2017. In: KARI, Jarkko, ed. and others. Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings. Cham: Springer, 2017, pp. 187-197. Lecture Notes in Computer Science. 10307. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-58740-0. Available under: doi: 10.1007/978-3-319-58741-7_19BibTex
@inproceedings{Carl2017-05-12Koepk-41575, year={2017}, doi={10.1007/978-3-319-58741-7_19}, title={Koepke Machines and Satisfiability for Infinitary Propositional Languages}, number={10307}, isbn={978-3-319-58740-0}, issn={0302-9743}, publisher={Springer}, address={Cham}, series={Lecture Notes in Computer Science}, booktitle={Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings}, pages={187--197}, editor={Kari, Jarkko}, author={Carl, Merlin and Löwe, Benedikt and Rin, Benjamin G.} }
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/41575"> <dc:creator>Rin, Benjamin G.</dc:creator> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/41575"/> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/> <dc:language>eng</dc:language> <dcterms:title>Koepke Machines and Satisfiability for Infinitary Propositional Languages</dcterms:title> <dc:creator>Löwe, Benedikt</dc:creator> <dc:contributor>Löwe, Benedikt</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-02-23T10:06:24Z</dcterms:available> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Rin, Benjamin G.</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/> <dcterms:abstract xml:lang="eng">We consider complexity theory for Koepke machines, also known as Ordinal Turing Machines (OTMs), and define infinitary complexity classes ∞-P and ∞-NP and the OTM analogue of the satisfiability problem, denoted by ∞-SAT. We show that ∞-SAT is in ∞-NP and ∞-NP-hard (i.e., the problem is ∞-NP-complete), but not OTM decidable.</dcterms:abstract> <dc:creator>Carl, Merlin</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-02-23T10:06:24Z</dc:date> <dcterms:issued>2017-05-12</dcterms:issued> <dc:contributor>Carl, Merlin</dc:contributor> </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
Ja