Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-19T05:17:00.066Z Has data issue: false hasContentIssue false

Complexity of interpolation and related problems in positive calculi

Published online by Cambridge University Press:  12 March 2014

Larisa Maksimova*
Affiliation:
Institute of Mathematics, Siberian Division of Russian Academy of Sciences, 630090 Novosibirsk, Russia, E-mail: lmaksi@math.nsc.ru

Abstract

We consider the problem of recognizing important properties of logical calculi and find complexity bounds for some decidable properties. For a given logical system L, a property P of logical calculi is called decidable over L if there is an algorithm which for any finite set Ax of new axiom schemes decides whether the calculus L + Ax has the property P or not. In [11] the complexity of tabularity, pre-tabularity. and interpolation problems over the intuitionistic logic Int and over modal logic S4 was studied, also we found the complexity of amalgamation problems in varieties of Heyting algebras and closure algebras.

In the present paper we deal with positive calculi. We prove NP-completeness of tabularity, DP-hardness of pretabularity and PSPACE-completeness of interpolation problem over Int+. In addition to above-mentioned properties, we consider Beth's definability properties. Also we improve some complexity bounds for properties of superintuitionistic calculi.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable