On the complexity of some substructural logics

• Autorzy: Buszkowski, W.
• Języki publikacji: EN

Abstrakty

EN

We use a syntactic interpretation of MALL in BCI with logical and , defined in [5], to prove the undecidability of the consequence relations for BCI with logical and and BCI with logical or , and the NP-completeness of BCI. Similar results are obtained for a variant of the Lambek calculus.

• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2008
• Tom: No. 43
• Strony: 5-24
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Buszkowski, W.

Bibliografia

• [1] F. Belardinelli, P. Jipsen and H. Ono, Algebraic Aspects of Cut Elimination, Studia Logica 77 (2004), pp. 209–240.
• [2] W. Buszkowski, Some decision problems in the theory of syntactic categories, Zeitschrift f. mathematische Logik u. Grundlagen d. Math. 28 (1982), pp. 539–548.
• [3] W. Buszkowski, Completeness results for Lambek Syntactic Calculus, Zeitschrift f..math. Logik u. Grundlagen d. Math., 32 (1986), pp. 13–28.
• [4] W. Buszkowski, The Finite Model Property for BCI and Related Systems, Studia Logica 57 (1996), pp. 303–323.
• [5] W. Buszkowski, Finite Models of Some Substructural Logics, Mathematical Logic Quarterly 48 (2002), pp. 63–72.
• [6] W. Buszkowski, Lambek Calculus with Nonlogical Axioms, in: C. Casadio, P.J. Scott, R. Seely (eds.), Language and Grammar. Studies in Mathematical Linguistics and Natural Language, CSLI Lecture Notes 168, Stanford, 2005, pp. 77–93.
• [7] J-Y. Girard, Linear logic, Theoretical Computer Science 50, (1987), pp. 1–102.
• [8] J-Y. Girard, Y. Lafont, L. Regnier (eds.), Advances in Linear Logic, Cambridge University Press, 1995.
• [9] M.I. Kanovich, The multiplicative fragment of linear logic is NP-complete, Technical Report X-91-13, Institute for Logic, Language and Information, Amsterdam, 1991.
• [10] M.I. Kanovich, The Direct Simulation of Minsky Machines in Linear Logic, in: [8], pp. 123–145.
• [11] J. Lambek, The mathematics of sentence structure, American Mathematical Monthly 65 (1958), pp. 154–170.
• [12] P. Lincoln, Deciding Provability of Linear Logic Formulas, in: [8], pp. 109–122.
• [13] P. Lincoln, J.Mitchell, A. Scedrov, N. Shankar, Decision problems for propositional linear logic, Annals of Pure and Applied Logic 56 (1992), pp. 239–311.
• [14] P. Lincoln, T. Winkler, Constant-Only Multiplicative Linear Logic is NP-Complete,Theoretical Computer Science 135 (1994), pp. 155–169.
• [15] H. Ono, Semantics of Substructural Logics, in: [18], pp. 259–291.
• [16] H. Ono, Decidabilty and finite model property of substructural logics, in: J. Ginzburg et al., eds., The Tbilisi Symposium on Logic, Language and Computation: Selected Papers, CSLI Publications, 1998, pp. 263–274.
• [17] M. Pentus, Lambek calculus is NP-complete, Theoretical Computer Science 357 (2006), pp. 186–201.
• [18] P. Schroeder-Heister, K. Dosen (eds.), Substructural Logics, Clarendon Press, Oxford, 1993.
• [19] D.N. Yetter, Quantales and (Non-Commutative) Linear Logic, Journal of Symbolic Logic 55 (1990), pp. 41–64