Pregled bibliografske jedinice broj: 983020
Complexity of the interpretability logic IL
Complexity of the interpretability logic IL // Logic journal of the igpl, 27 (2019), 1; 1-7 doi:10.1093/jigpal/jzy015 (međunarodna recenzija, članak, znanstveni)
CROSBI ID: 983020 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
Complexity of the interpretability logic IL
Autori
Mikec, Luka ; Pakhomov, Fedor ; Vuković, Mladen
Izvornik
Logic journal of the igpl (1367-0751) 27
(2019), 1;
1-7
Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni
Ključne riječi
interpretability logic ; PSPACE-completeness
Sažetak
We show that the decision problem for the basic system of interpretability logic IL is PSPACE- complete. For this purpose we present an algorithm which uses polynomial space w.r.t. the complexity of a given formula. The existence of such algorithm, together with the previously known PSPACE-hardness of the closed fragment of IL, implies PSPACE-completeness.
Izvorni jezik
Engleski
Znanstvena područja
Matematika
POVEZANOST RADA
Projekti:
HRZZ-UIP-2017-05-9219 - Formalno rasuđivanje i semantike (FORMALS) (Perkov, Tin, HRZZ - 2017-05) ( CroRIS)
Ustanove:
Prirodoslovno-matematički fakultet, Matematički odjel, Zagreb,
Prirodoslovno-matematički fakultet, Zagreb
Citiraj ovu publikaciju:
Časopis indeksira:
- Web of Science Core Collection (WoSCC)
- Science Citation Index Expanded (SCI-EXP)
- SCI-EXP, SSCI i/ili A&HCI
- Scopus
