Koepke Machines and Satisfiability for Infinitary Propositional Languages
| Type of Publication: | Contribution to a conference collection |
| Publication status: | Published |
| Author: | Carl, Merlin; Löwe, Benedikt; Rin, Benjamin G. |
| Year of publication: | 2017 |
| Conference: | 13th Conference on Computability in Europe, CiE 2017, Jun 12, 2017 - Jun 16, 2017, Turku, Finland |
| Published in: | Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings / Kari, Jarkko et al. (ed.). - Cham : Springer, 2017. - (Lecture Notes in Computer Science ; 10307). - pp. 187-197. - ISSN 0302-9743. - eISSN 1611-3349. - ISBN 978-3-319-58740-0 |
| DOI (citable link): | https://dx.doi.org/10.1007/978-3-319-58741-7_19 |
| Summary: |
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.
|
| Subject (DDC): | 510 Mathematics |
| Bibliography of Konstanz: | Yes |
Cite This
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||
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, Jun 12, 2017 - Jun 16, 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, 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>
This item appears in the following Collection(s)
Search KOPS
Browse
My Account
