Naslov
Complexity of the interpretability logics ILW and ILP

Autori
Mikec, Luka

Izvornik
Logic journal of the igpl (1367-0751) 31 (2023), 1; 194-213

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
modal logic ; interpretability logic ; complexity ; PSPACE ; Veltman semantics

Sažetak
The interpretability logic ILP is the interpretability logic of all sufficiently strong Σ1-sound finitely axiomatised theories, such as the Gödel-Bernays set theory. The interpretability logic IL is a strict subset of the intersection of the interpretability logics of all so-called reasonable theories, IL(All). It is known that both ILP and ILW are decidable, however their complexity has not been resolved previously. In [10] it was shown that the basic interpretability logic IL is PSPACE-complete. Here we prove the same for ILP and ILW.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA