COMPLEXITY OF SOME PROBLEMS IN MODAL AND INTUITIONISTIC CALCULI
This chapter investigates the problem of recognizing properties of logical calculi. Complexity bounds for interpolation and some other problems over Int and S4 are found. It is proved that the tabularity problems over both Int and S4 are NP-complete, and the interpolation problems over both Int and Grz are PSPACE-complete, both CIP and IPD problems over S4 are in coNEXP and PSPACE-hard. Complexity bounds for pre-tabularity and local tabularity, and for amalgamation properties in varieties are also found.
Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
If you think you should have access to this title, please contact your librarian.