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

Napredna pretraga

Pregled bibliografske jedinice broj: 1032551

Decidability and Complexity of Some Interpretability Logics


Mikec, Luka; Perkov, Tin; Vuković, Mladen
Decidability and Complexity of Some Interpretability Logics // Logic and Applications 2017 Book of Abstracts
Dubrovnik, Hrvatska, 2017. str. 29-31 (predavanje, nije recenziran, sažetak, znanstveni)


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

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
Logic and Applications 2017 Book of Abstracts / - , 2017, 29-31

Skup
Logic and Applications 2017

Mjesto i datum
Dubrovnik, Hrvatska, 18-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


Ustanove
Prirodoslovno-matematički fakultet, Zagreb,
Učiteljski fakultet, Zagreb,
Sveučilište u Rijeci - Odjel za matematiku

Profili:

Avatar Url Mladen Vuković (autor)

Avatar Url Tin Perkov (autor)

Avatar Url Luka Mikec (autor)

Citiraj ovu publikaciju

Mikec, Luka; Perkov, Tin; Vuković, Mladen
Decidability and Complexity of Some Interpretability Logics // Logic and Applications 2017 Book of Abstracts
Dubrovnik, Hrvatska, 2017. str. 29-31 (predavanje, nije recenziran, sažetak, znanstveni)
Mikec, L., Perkov, T. & Vuković, M. (2017) Decidability and Complexity of Some Interpretability Logics. U: Logic and Applications 2017 Book of Abstracts.
@article{article, year = {2017}, pages = {29-31}, keywords = {interpretability logic, decidability, complexity}, title = {Decidability and Complexity of Some Interpretability Logics}, keyword = {interpretability logic, decidability, complexity}, publisherplace = {Dubrovnik, Hrvatska} }