Koepke Machines and Satisfiability for Infinitary Propositional Languages
| dc.contributor.author | Carl, Merlin | |
| dc.contributor.author | Löwe, Benedikt | |
| dc.contributor.author | Rin, Benjamin G. | |
| dc.date.accessioned | 2018-02-23T10:06:24Z | |
| dc.date.available | 2018-02-23T10:06:24Z | |
| dc.date.issued | 2017-05-12 | eng |
| dc.description.abstract | 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. | eng |
| dc.description.version | published | eng |
| dc.identifier.doi | 10.1007/978-3-319-58741-7_19 | eng |
| dc.identifier.uri | https://kops.uni-konstanz.de/handle/123456789/41575 | |
| dc.language.iso | eng | eng |
| dc.subject.ddc | 510 | eng |
| dc.title | Koepke Machines and Satisfiability for Infinitary Propositional Languages | eng |
| dc.type | INPROCEEDINGS | eng |
| dspace.entity.type | Publication | |
| kops.citation.bibtex | @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.}
} | |
| kops.citation.iso690 | 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_19 | deu |
| kops.citation.iso690 | 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, 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 | eng |
| kops.citation.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> | |
| kops.conferencefield | 13th Conference on Computability in Europe, CiE 2017, 12. Juni 2017 - 16. Juni 2017, Turku, Finland | deu |
| kops.date.conferenceEnd | 2017-06-16 | eng |
| kops.date.conferenceStart | 2017-06-12 | eng |
| kops.flag.knbibliography | true | |
| kops.location.conference | Turku, Finland | eng |
| kops.sourcefield | KARI, Jarkko, ed. and others. <i>Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings</i>. 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 | deu |
| kops.sourcefield.plain | 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 | deu |
| kops.sourcefield.plain | 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 | eng |
| kops.title.conference | 13th Conference on Computability in Europe, CiE 2017 | eng |
| relation.isAuthorOfPublication | 9fa2dd55-adfa-43d0-885c-3eee0ff14362 | |
| relation.isAuthorOfPublication.latestForDiscovery | 9fa2dd55-adfa-43d0-885c-3eee0ff14362 | |
| source.bibliographicInfo.fromPage | 187 | eng |
| source.bibliographicInfo.seriesNumber | 10307 | eng |
| source.bibliographicInfo.toPage | 197 | eng |
| source.contributor.editor | Kari, Jarkko | |
| source.flag.etalEditor | true | eng |
| source.identifier.eissn | 1611-3349 | eng |
| source.identifier.isbn | 978-3-319-58740-0 | eng |
| source.identifier.issn | 0302-9743 | eng |
| source.publisher | Springer | eng |
| source.publisher.location | Cham | eng |
| source.relation.ispartofseries | Lecture Notes in Computer Science | eng |
| source.title | Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings | eng |