Koepke Machines and Satisfiability for Infinitary Propositional Languages

Publikationstyp: Beitrag zu einer Konferenz
Publikationsstatus: Published
Autor/innen: Carl, Merlin; Löwe, Benedikt; Rin, Benjamin G.
Erscheinungsjahr: 2017
Konferenz: 13th Conference on Computability in Europe, CiE 2017, 12. Jun 2017 - 16. Jun 2017, Turku, Finland
Erschienen in: Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings / Kari, Jarkko et al. (Hrsg.). - Cham : Springer, 2017. - (Lecture Notes in Computer Science ; 10307). - S. 187-197. - ISSN 0302-9743. - eISSN 1611-3349. - ISBN 978-3-319-58740-0
DOI (zitierfähiger Link): https://dx.doi.org/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.
Fachgebiet (DDC): 510 Mathematik
Universitätsbibliographie: Ja

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

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. Jun 2017 - 16. Jun 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. 13th Conference on Computability in Europe, CiE 2017. Turku, Finland, 12. Jun 2017 - 16. Jun 2017. Cham:Springer, pp. 187-197. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-58740-0. Available under: doi: 10.1007/978-3-319-58741-7_19

@inproceedings{Carl2017-05-12Koepk-41575, title={Koepke Machines and Satisfiability for Infinitary Propositional Languages}, year={2017}, doi={10.1007/978-3-319-58741-7_19}, number={10307}, isbn={978-3-319-58740-0}, issn={0302-9743}, address={Cham}, publisher={Springer}, 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 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/rdf/resource/123456789/41575"> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/39"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/41575"/> <dcterms:title>Koepke Machines and Satisfiability for Infinitary Propositional Languages</dcterms:title> <dc:contributor>Löwe, Benedikt</dc:contributor> <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> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/39"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-02-23T10:06:24Z</dc:date> <dc:contributor>Carl, Merlin</dc:contributor> <dc:creator>Rin, Benjamin G.</dc:creator> <dc:creator>Carl, Merlin</dc:creator> <dc:language>eng</dc:language> <dc:creator>Löwe, Benedikt</dc:creator> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-02-23T10:06:24Z</dcterms:available> <dc:contributor>Rin, Benjamin G.</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:issued>2017-05-12</dcterms:issued> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto