scientific article; zbMATH DE number 3995647

From MaRDI portal
Publication:4723713





[For the entire collection see Zbl 0596.00004.] This paper enlarges and continues an earlier one of the same author [Polynomial finite approximability of modal and superintuitionistic logics (Russian), Mat. Logika, Mat. Ling., Teor. Algor., Kalinin. Gos. Univ., Kalinin, 75-83 (1983)]. Taking as complexity function of a logic L the function \(f_ L:\omega \to \omega\) with \(f_ L(n)\) the minimal cardinality of countermodels for all non-theorems of L of length \(\leq n\), it is shown in a first part that some intermediate logics and also some modal logics may have rapidly growing complexity functions. In a second part, the NP- reps. PSPACE-completeness of the satisfiability problem is proved for some intermediate logics.




Cited in
(36)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723713)