Unit:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούLibrary of the School of Science
Supervisors info:
Κ. Κούτρας Επίκ. Καθηγητής Πανεπιστήμιο Πελοποννήσου (Επιβλέπων), Ε. Ζάχος Καθηγητής ΕΜΠ, Κ. Δημητρακόπουλος Καθηγητής ΕΚΠΑ, Π. Ροντογιάννης Αναπλ. Καθηγητής ΕΚΠΑ
Original Title:
Αποκρισιμότητα και πολυπλοκότητα της τροπικής λογικής
Translated title:
Decidability and complexity of modal logic
Summary:
In the present dissertation we study modal logic, with an emphasis on its
applications in computer science. One of the most important reasons for the
wide use of modal logic in many areas of computer science (and other
disciplines) is its behaviour with regard to decidability: modal logic is
decidable and remains decidable after many powerful extensions while, at the
same time, it is expressive enough to be useful in practice. One could
juxtapose this behaviour with the behaviour of first-order logic, which is even
in the simplest case undecidable. Moreover, even though the computational
complexity of modal logic is in theory very high, in practice the problems that
force such complexity are very rare. Initially we present relevant results, and
we then try to interpret this behaviour by considering relevant fragments of
first-order logic, which effectively express the "spirit" of modal logic.
Keywords:
Modal logic, Computability theory, Computational complexity, Fragments of first-order logic, Two-variable fragment
