Logo
User: Guest  Login
Authors:
Krommes, Gisela 
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. 
Date oral examination:
08.01.2020 
Publication date:
28.07.2020 
Year:
2020 
Pages (Book):
182 
Language:
Englisch 
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...    »
 
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