Koepke Machines and Satisfiability for Infinitary Propositional Languages

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2017
Autor:innen
Löwe, Benedikt
Rin, Benjamin G.
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Gesperrt bis
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
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Datensätze
Zitieren
ISO 690CARL, 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
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.}
}
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
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen