KOPS - The Institutional Repository of the University of Konstanz

Koepke Machines and Satisfiability for Infinitary Propositional Languages

Koepke Machines and Satisfiability for Infinitary Propositional Languages

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