Logo
Benutzer: Gast  Login
Autoren:
Krommes, Gisela 
Dokumenttyp:
Dissertation / Thesis 
Titel:
The Complexity of the Product Logics K4xS5 and S4xS5 and of the Logic SSL of Subset Spaces 
Betreuer:
Hertling, Peter, Prof. Dr. 
Gutachter:
Hertling, Peter, Prof. Dr.; Sattler, Ulrike, Prof. Dr. 
Tag der mündlichen Prüfung:
08.01.2020 
Publikationsdatum:
28.07.2020 
Jahr:
2020 
Seiten (Monografie):
182 
Sprache:
Englisch 
Schlagwörter:
Modallogik ; Produktlogik ; Komplexitätstheorie ; Teilmenge ; Algorithmus ; Erfüllbarkeitsproblem ; Hochschulschrift 
Stichwörter:
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 
Fakultät:
Fakultät für Informatik 
Institut:
INF 1 - Institut für Theoretische Informatik, Mathematik und Operations Research 
Professur:
Hertling, Peter 
Open Access ja oder nein?:
Ja / Yes