{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T08:20:50Z","timestamp":1775463650473,"version":"3.50.1"},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":4394,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2002,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem of recognizing important properties of logical calculi and find complexity bounds for some decidable properties. For a given logical system<jats:italic>L<\/jats:italic>, a property P of logical calculi is called decidable over<jats:italic>L<\/jats:italic>if there is an algorithm which for any finite set<jats:italic>Ax<\/jats:italic>of new axiom schemes decides whether the calculus<jats:italic>L<\/jats:italic>+<jats:italic>Ax<\/jats:italic>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.<\/jats:p><jats:p>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<jats:sup>+<\/jats:sup>. In addition to above-mentioned properties, we consider Beth's definability properties. Also we improve some complexity bounds for properties of superintuitionistic calculi.<\/jats:p>","DOI":"10.2178\/jsl\/1190150051","type":"journal-article","created":{"date-parts":[[2007,12,13]],"date-time":"2007-12-13T19:12:10Z","timestamp":1197573130000},"page":"397-408","source":"Crossref","is-referenced-by-count":6,"title":["Complexity of interpolation and related problems in positive calculi"],"prefix":"10.1017","volume":"67","author":[{"given":"Larisa","family":"Maksimova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200010069_ref009","doi-asserted-by":"publisher","DOI":"10.1137\/0206033"},{"key":"S0022481200010069_ref018","volume-title":"Computational complexity","author":"Papadimitriou","year":"1994"},{"key":"S0022481200010069_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90049-4"},{"key":"S0022481200010069_ref006","first-page":"67","volume-title":"Handbook of theoretical computer science","volume":"A","author":"Johnson","year":"1990"},{"key":"S0022481200010069_ref007","first-page":"389","volume":"25","author":"Kreisel","year":"1960","journal-title":"Explicit definability in intuitionistic logic"},{"key":"S0022481200010069_ref011","first-page":"118","volume-title":"Logic colloquium '99, Abstracts","volume":"6","author":"Maksimova","year":"1999"},{"key":"S0022481200010069_ref002","first-page":"269","volume":"22","author":"Craig","year":"1957","journal-title":"Three uses of Herbrand-Gentzen theorem in relating model theory"},{"key":"S0022481200010069_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(99)00049-4"},{"key":"S0022481200010069_ref012","unstructured":"Maksimova L. L. , Implicit definability and positive logics, to appear in Algebra and Logic ."},{"key":"S0022481200010069_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BF02330744"},{"key":"S0022481200010069_ref020","volume-title":"The mathematics of metamathematics","author":"Rasiowa","year":"1963"},{"key":"S0022481200010069_ref016","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010208217965"},{"key":"S0022481200010069_ref005","first-page":"67","article-title":"Intermediate prepositional logics. A survey","volume":"5","author":"Hosoi","year":"1973","journal-title":"Journal of Tsuda College"},{"key":"S0022481200010069_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF01670006"},{"key":"S0022481200010069_ref001","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198537793.001.0001","volume-title":"Modal logics","author":"Chagrov","year":"1997"},{"key":"S0022481200010069_ref017","doi-asserted-by":"publisher","DOI":"10.1017\/S0027763000011715"},{"key":"S0022481200010069_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90046-1"},{"key":"S0022481200010069_ref008","first-page":"255","volume-title":"11th Sovjet algebraic colloquium, Abstracts","author":"Kuznetsov","year":"1971"},{"key":"S0022481200010069_ref014","first-page":"1281","article-title":"Craig's interpolation theorem and amalgamable varieties","volume":"237","author":"Maksimova","year":"1977","journal-title":"Doklady AN SSSR"},{"key":"S0022481200010069_ref019","first-page":"115","volume-title":"Proceedings 20th IEEE symposium on foundations of computer science","author":"Pratt","year":"1979"},{"key":"S0022481200010069_ref021","volume-title":"Dissertation","author":"Spaan","year":"1992"},{"key":"S0022481200010069_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90006-9"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200010069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T10:41:51Z","timestamp":1708425711000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200010069\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,3]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,3]]}},"alternative-id":["S0022481200010069"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1190150051","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,3]]}}}