Naslov
Decidability and Complexity of Some Interpretability Logics

Autori
Mikec, Luka ; Perkov, Tin ; Vuković, Mladen

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
Book of Abstracts of the 6 th International Conference on Logic and Applications - LAP 2017 / - , 2017, 29-31

Skup
Logic and Applications 2017

Mjesto i datum
Dubrovnik, Hrvatska, 18.09.2017. - 22.09.2017

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Nije recenziran

Ključne riječi
interpretability logic ; decidability ; complexity

Sažetak
The usual way to prove decidability of a modal logic with relational (Kripke-style) semantics is to prove it has the finite model property. Interpretability logics are usually interpreted on classes of Veltman models, or generalized Veltman models, which are both extensions of Kripke models. We will describe an approach to proving the finite model property by defining a certain filtration of generalized Veltman models. We use this approach to prove decidability of the logic ILM0 and ILW*. We also study computational complexity of logics based on Veltman models. We prove that the logic IL is in PSPACE ; and since it was already known to be PSPACE-hard, we conclude that it is PSPACE-complete. We will comment on complexity of some other interpretability logics with finite model property.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA