Pretražite po imenu i prezimenu autora, mentora, urednika, prevoditelja

Napredna pretraga

Pregled bibliografske jedinice broj: 1032553

Complexity of the interpretability logic IL


Mikec, Luka; Pakhomov, Fedor; Vuković, Mladen
Complexity of the interpretability logic IL // Logic and Applications 2018 Book of Abstracts
Dubrovnik, Hrvatska, 2018. str. 54-55 (predavanje, nije recenziran, sažetak, znanstveni)


CROSBI ID: 1032553 Za ispravke kontaktirajte CROSBI podršku putem web obrasca

Naslov
Complexity of the interpretability logic IL

Autori
Mikec, Luka ; Pakhomov, Fedor ; Vuković, Mladen

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

Izvornik
Logic and Applications 2018 Book of Abstracts / - , 2018, 54-55

Skup
Logic and Applications 2018

Mjesto i datum
Dubrovnik, Hrvatska, 24-28.09.2018

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Nije recenziran

Ključne riječi
interpretability logic, Veltman semantics, decidability, complexity, PSPACE

Sažetak
This talk is based on the paper [MPV18]. Computational complexity of modal logics was first studied by Ladner [Lad77]. Various tableau– based methods were used in proofs of PSPACE– decidability of a number of modal logics (like K, K4, S4 etc ; see [Lad77] and [Spa93]). PSPACE– completeness of the satisfiability problem (and also of the decision problem, since co-PSPACE = PSPACE) for the closed fragments of modal systems K4, S4, Grz and GL is proved by Chagrov and Rybakov [CR03]. Shapirovsky [Sha10] proved the PSPACE– decidability of propositional polymodal provability logic GLP. PSPACE–completeness of the closed fragment of the system GLP is proved by Pakhomov in [Pak14]. The interpretability logic IL, introduced by Visser [Vis90], is an extension of provability logic with a binary modal operator B. This operator stands for interpretability, considered as a relation between extensions of a fixed theory. Bou and Joosten proved in [BJ11] that the decidability problem for the closed fragment of IL is PSPACE–hard. We consider the complexity problem for interpretability logic and prove that the system IL is PSPACE–complete. Our constructions can be seen as generalizations of the constructions by Boolos presented in [Boo96] (Chapter 10). If we restrict our work to GL, the resulting method is very similiar to the one given by Boolos, up to the terminology. Our method can also be seen as extending the method presented in [Sha10], of proving PSPACE– completeness (monomodal case), and has similarities with the proofs od completeness in [GJ08] and [GJ11]. We will comment on extending this approach to other interpretability logics.

Izvorni jezik
Engleski

Znanstvena područja
Matematika



POVEZANOST RADA


Projekt / tema
UIP-05-2017-9219

Ustanove
Prirodoslovno-matematički fakultet, Zagreb

Profili:

Avatar Url Mladen Vuković (autor)

Avatar Url Luka Mikec (autor)

Citiraj ovu publikaciju

Mikec, Luka; Pakhomov, Fedor; Vuković, Mladen
Complexity of the interpretability logic IL // Logic and Applications 2018 Book of Abstracts
Dubrovnik, Hrvatska, 2018. str. 54-55 (predavanje, nije recenziran, sažetak, znanstveni)
Mikec, L., Pakhomov, F. & Vuković, M. (2018) Complexity of the interpretability logic IL. U: Logic and Applications 2018 Book of Abstracts.
@article{article, year = {2018}, pages = {54-55}, keywords = {interpretability logic, Veltman semantics, decidability, complexity, PSPACE}, title = {Complexity of the interpretability logic IL}, keyword = {interpretability logic, Veltman semantics, decidability, complexity, PSPACE}, publisherplace = {Dubrovnik, Hrvatska} }