engleski

Complexity of the interpretability logics ILW and ILP

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.

modal logic ; interpretability logic ; complexity ; PSPACE ; Veltman semantics

nije evidentirano