Complexity of admissible rules

1. Blackburn P., Venema Y. and Rijke M. (2001). Modal logic, Cambridge Tracts in Theoretical Computer Science, vol. 53. Cambridge University Press, Cambridge

   Google Scholar 

2. Bull R.A. (1966). That all normal extensions of S4.3 have the finite model property. Zeitschrift mathematische Logik Grundlagen Mathematik 12: 341–344

   MathSciNet  Google Scholar 

3. Chagrov, A.V.: On the complexity of propositional logics. In: Complexity problems in Mathematical Logic, pp. 80–90. Kalinin State University (1985) (in Russian)

4. Chagrov A.V. (1992). A decidable modal logic with the undecidable admissibility problem for inference rules. Algebra Logic 31: 53–55

   Article  MathSciNet  Google Scholar 

5. Chagrov A.V. and Zakharyaschev M. (1997). Modal Logic. Oxford Logic Guides, vol. 35. Oxford University Press, Oxford

   Google Scholar 

6. Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation SIAM-AMS Proceedings, vol. 7, pp. 43–73 (1974)

7. Friedman H.M. (1975). One hundred and two problems in mathematical logic. J. Symbolic Logic 40(2): 113–129

   Article  MathSciNet  Google Scholar 

8. Ghilardi S. (1999). Unification in intuitionistic logic. J. Symbolic Logic 64(2): 859–880

   Article  MathSciNet  Google Scholar 

9. Ghilardi S. (2000). Best solving modal equations. Ann. Pure Appl. Logic 102(3): 183–198

   Article  MathSciNet  Google Scholar 

10. Ghilardi S. (2002). A resolution/tableaux algorithm for projective approximations in IPC. Logic J. IGPL 10(3): 229–243

    Article  MathSciNet  Google Scholar 

11. Iemhoff R. (2001). On the admissible rules of intuitionistic propositional logic. J. Symbolic Logic 66(1): 281–294

    Article  MathSciNet  Google Scholar 

12. Iemhoff R. (2005). Intermediate logics and Visser’s rules. Notre Dame J. Formal Logic 46(1): 65–81

    Article  MathSciNet  Google Scholar 

13. Iemhoff R. (2006). On the rules of intermediate logics. Arch. Math. Logic 45(5): 581–599

    Article  MathSciNet  Google Scholar 

14. Jeřábek E. (2005). Admissible rules of modal logics. J. Logic Comput. 15(4): 411–431

    Article  MathSciNet  Google Scholar 

15. Kuznetsov, A.V.: On superintuitionistic logics. In: Proceedings of the International Congress of Mathematicians (Vancouver), pp. 243–249 (1975)

16. Ladner R.E. (1977). The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput. 6(3): 467–480

    Article  MathSciNet  Google Scholar 

17. Papadimitriou C.H. (1994). Computational complexity. Addison-Wesley, Reading

    MATH  Google Scholar 

18. Rybakov V.V. (1997). Admissibility of logical inference rules. Studies in Logic and the Foundations of Mathematics, vol 136. Elsevier, Amsterdam

    Google Scholar 

19. Spaan, E.: Complexity of modal logics. Ph.D. thesis, University of Amsterdam (1993)

20. Statman R. (1979). Intuitionistic propositional logic is polynomial-space complete. Theor. Comput. Sci. 9(1): 67–72

    Article  MathSciNet  Google Scholar 

21. Zakharyaschev M. (1996). Canonical formulas for K4. Part II: Cofinal subframe logics. J. Symbolic Logic 61(2): 421–449

    Article  MathSciNet  Google Scholar 

Download references