Login
Document type:
Dissertation / Thesis
Title:
The Complexity of the Product Logics K4xS5 and S4xS5 and of the Logic SSL of Subset Spaces
Advisor:
Hertling, Peter, Prof. Dr.
Referee:
Hertling, Peter, Prof. Dr.; Sattler, Ulrike, Prof. Dr.
Submission date:
11.09.2019
Date oral examination:
08.01.2020
Publication date:
28.07.2020
Year:
2020
Pages (Book):
182
Language:
Englisch
Subject:
Modallogik ; Produktlogik ; Komplexitätstheorie ; Teilmenge ; Algorithmus ; Erfüllbarkeitsproblem ; Hochschulschrift
Keywords:
bimodal product logics, subset space logic, satisfiability problem, complexity theory, EXPSPACE-completeness
Abstract:
We show that the satisfiability problems of the bimodal product logics K4xS5 and S4xS5 and of the bimodal logic of subset spaces SSL are EXPSPACE-complete. In fact, on the one hand we construct for these three problems decision algorithms working even in ESPACE. The heart of the proof, that on the other hand these problems are EXPSPACE-hard, is a reduction, computable in logarithmic space, of the word problem for so called Alternating Turing machines working in exponential time to the satisfiabili... »
DDC notation:
004.015113
Department:
Fakultät für Informatik
Institute:
INF 1 - Institut für Theoretische Informatik, Mathematik und Operations Research
Chair:
Hertling, Peter
Open Access yes or no?:
Ja / Yes
BibTeX