Koepke Machines and Satisfiability for Infinitary Propositional Languages

Merlin Carl; Benedikt Löwe; Benjamin Rin

doi:10.1007/978-3-319-58741-7_19

Koepke Machines and Satisfiability for Infinitary Propositional Languages

Merlin Carl, Benedikt Löwe, Benjamin Rin

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

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.

Original language	English
Title of host publication	Unveiling Dynamics and Complexity
Subtitle of host publication	13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings
Editors	Jarkko Kari, Florin Manea, Ion Petre
Place of Publication	Cham
Publisher	Springer
Pages	187-197
Number of pages	11
ISBN (Electronic)	978-3-319-58741-7
ISBN (Print)	978-3-319-58740-0
DOIs	https://doi.org/10.1007/978-3-319-58741-7_19
Publication status	Published - May 2017

Publication series

Name	Lecture Notes in Computer Science
Volume	10307

Access to Document

10.1007/978-3-319-58741-7_19

10.1007%2F978-3-319-58741-7_19Final published version, 217 KBLicence: Taverne

Cite this

Carl, M., Löwe, B., & Rin, B. (2017). Koepke Machines and Satisfiability for Infinitary Propositional Languages. In J. Kari, F. Manea, & I. Petre (Eds.), Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings (pp. 187-197). (Lecture Notes in Computer Science ; Vol. 10307). Springer. https://doi.org/10.1007/978-3-319-58741-7_19

Carl, Merlin ; Löwe, Benedikt ; Rin, Benjamin. / Koepke Machines and Satisfiability for Infinitary Propositional Languages. Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings. editor / Jarkko Kari ; Florin Manea ; Ion Petre. Cham : Springer, 2017. pp. 187-197 (Lecture Notes in Computer Science ).

@inbook{839f84ef7c344e2d9d08a67e7bcfb59d,

title = "Koepke Machines and Satisfiability for Infinitary Propositional Languages",

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.",

author = "Merlin Carl and Benedikt L{\"o}we and Benjamin Rin",

year = "2017",

month = may,

doi = "10.1007/978-3-319-58741-7_19",

language = "English",

isbn = "978-3-319-58740-0",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "187--197",

editor = "Kari, {Jarkko } and Florin Manea and Ion Petre",

booktitle = "Unveiling Dynamics and Complexity",

}

Carl, M, Löwe, B & Rin, B 2017, Koepke Machines and Satisfiability for Infinitary Propositional Languages. in J Kari, F Manea & I Petre (eds), Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings. Lecture Notes in Computer Science , vol. 10307, Springer, Cham, pp. 187-197. https://doi.org/10.1007/978-3-319-58741-7_19

Koepke Machines and Satisfiability for Infinitary Propositional Languages. / Carl, Merlin; Löwe, Benedikt; Rin, Benjamin.
Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings. ed. / Jarkko Kari; Florin Manea; Ion Petre. Cham: Springer, 2017. p. 187-197 (Lecture Notes in Computer Science ; Vol. 10307).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Koepke Machines and Satisfiability for Infinitary Propositional Languages

AU - Carl, Merlin

AU - Löwe, Benedikt

AU - Rin, Benjamin

PY - 2017/5

Y1 - 2017/5

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-58741-7_19

DO - 10.1007/978-3-319-58741-7_19

M3 - Chapter

SN - 978-3-319-58740-0

T3 - Lecture Notes in Computer Science

SP - 187

EP - 197

BT - Unveiling Dynamics and Complexity

A2 - Kari, Jarkko

A2 - Manea, Florin

A2 - Petre, Ion

PB - Springer

CY - Cham

ER -

Carl M, Löwe B, Rin B. Koepke Machines and Satisfiability for Infinitary Propositional Languages. In Kari J, Manea F, Petre I, editors, Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings. Cham: Springer. 2017. p. 187-197. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-319-58741-7_19

Koepke Machines and Satisfiability for Infinitary Propositional Languages

Abstract

Publication series

Access to Document

Fingerprint

Cite this