Graduate studies at Western
Journal of Symbolic Logic 67 (1):397-408 (2002)
|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  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|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Grzegorz Malinowski (1977). Degrees of Maximality of Łukasiewicz-Like Sentential Calculi. Studia Logica 36 (3):213 - 228.
William C. Purdy (2002). Complexity and Nicety of Fluted Logic. Studia Logica 71 (2):177 - 198.
Riccardo Rosati (2001). A Sound and Complete Tableau Calculus for Reasoning About Only Knowing and Knowing at Most. Studia Logica 69 (1):171-191.
Larisa Maksimova (1995). On Variable Separation in Modal and Superintuitionistic Logics. Studia Logica 55 (1):99 - 112.
Martin Amerbauer (1996). Cut-Free Tableau Calculi for Some Propositional Normal Modal Logics. Studia Logica 57 (2-3):359 - 372.
Larisa L. Maksimova (1979). Interpolation Properties of Superintuitionistic Logics. Studia Logica 38 (4):419 - 428.
Larisa Maksimova (1991). Amalgamation and Interpolation in Normal Modal Logics. Studia Logica 50 (3-4):457 - 471.
Larisa Maksimova (2011). Interpolation and Definability Over the Logic Gl. Studia Logica 99 (1-3):249-267.
Małgorzata Porębska (1986). Interpolation and Amalgamation Properties in Varieties of Equivalential Algebras. Studia Logica 45 (1):35 - 38.
Larisa Maksimova (2006). Definability and Interpolation in Non-Classical Logics. Studia Logica 82 (2):271 - 291.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Total downloads1 ( #292,563 of 739,354 )
Recent downloads (6 months)0
How can I increase my downloads?