Log In

Koepke Machines and Satisfiability for Infinitary Propositional Languages

Files

10.1007_2F978_3_319_58741_7_19.pdf (217.08 KB)

Publication date

2017-05

Authors

Carl, Merlin
Löwe, Benedikt
Rin, BenjaminISNI 0000000456099134

Editors

Kari, Jarkko
Manea, Florin
Petre, Ion

Advisors

Supervisors

DOI

https://doi.org/10.1007/978-3-319-58741-7_19

Document Type

Part of book

Metadata

Show full item record

Collections

Utrecht University Repository
Open Access logo

License

taverne

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.

Keywords

Taverne

Citation

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

URI

https://dspace.library.uu.nl/handle/1874/358640