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

Napredna pretraga

Pregled bibliografske jedinice broj: 983020

Complexity of the interpretability logic IL


Mikec, Luka; Pakhomov, Fedor; Vuković, Mladen
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


Ustanove
Prirodoslovno-matematički fakultet, Matematički odjel, 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 journal of the igpl, 27 (2019), 1; 1-7 doi:10.1093/jigpal/jzy015 (međunarodna recenzija, članak, znanstveni)
Mikec, L., Pakhomov, F. & Vuković, M. (2019) Complexity of the interpretability logic IL. Logic journal of the igpl, 27 (1), 1-7 doi:10.1093/jigpal/jzy015.
@article{article, year = {2019}, pages = {1-7}, DOI = {10.1093/jigpal/jzy015}, keywords = {interpretability logic, PSPACE-completeness}, journal = {Logic journal of the igpl}, doi = {10.1093/jigpal/jzy015}, volume = {27}, number = {1}, issn = {1367-0751}, title = {Complexity of the interpretability logic IL}, keyword = {interpretability logic, PSPACE-completeness} }

Časopis indeksira:


  • Web of Science Core Collection (WoSCC)
    • Science Citation Index Expanded (SCI-EXP)
    • SCI-EXP, SSCI i/ili A&HCI
  • Scopus


Citati