×

Extensions of Lambek calculi. (English) Zbl 1500.03008

Casadio, Claudia (ed.) et al., Joachim Lambek: the interplay of mathematics, logic, and linguistics. Cham: Springer. Outst. Contrib. Log. 20, 105-134 (2021).
The Lambek calculus was introduced in [J. Lambek, Am. Math. Mon. 65, 154–170 (1958; Zbl 0080.00702)] under the name syntactic calculus, being called the associative Lambek calculus and denoted by \(\boldsymbol{L}\), while the nonassociative Lambek calculus, denoted by \(\boldsymbol{NL}\), was introduced by J. Lambek [“On the calculus of syntactic types”, in: R. Jakobson (ed.), Structure of language and its mathematical aspects. Providence: AMS. 166–178. (1961)], Residuated groupoids and semigroups are algebraic models of \(\boldsymbol{NL}\) and \(\boldsymbol{L}\), respectively. This paper aims to emphasize the role of the Lambek calculus in the realm of nonclassical logics. A better name for substructural logics could presumably be residuation logics. Products, also called multiplicative or intensional conjunction, tensor, fusion, is always related to the equivalences.
The synopsis of the paper goes as follows.
§ 2
discusses a residuation connection, which occupies a central position in the subject.
§ 3
recalls sequent systems for \(\boldsymbol{L}\) and \(\boldsymbol{NL}\), briefly discussing some properties of these systems (cut-elimination, completeness, decidability, complexity) as well as their role in categorical grammars. As a matter of fact, most results on these two logics were obtained by scholars with interest in linguistic applications.
§ 4
brings a survey of different substructural logics of intuitionistic nature giving up double negation. Since this area has been extensively explored since the 1980s, the author considers only some basic systems and their most fundamental properties. At the end, some related multi-modal logics are described.
§ 5
addresses (classical) linear logics, extending some logics from the previous section by the double negation laws. The presentation is very concise, considering only logics without exponentials with emphasis on noncommutative logics.
§ 6
contains some final comments.

For the entire collection see [Zbl 1470.03008].

MSC:

03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
03F52 Proof-theoretic aspects of linear logic and other substructural logics
Full Text: DOI

References:

[1] Abrusci, V.M. Classical conservative extensions of Lambek calculus.Studia Logica71, (2002) 277-314. · Zbl 1019.03018
[2] Ajdukiewicz, K. Die syntaktische Konnexit¨at.Studia Philosophica1, (1935), 1-27 . · Zbl 0015.33702
[3] Bar-Hillel, Y. A quasi-arithmetical notation for syntactic description.Language29, (1953), 47-58. · Zbl 0156.25402
[4] Bar-Hillel, Y., Gaifman, C. , and Shamir, E. On categorial and phrase structure grammars.Bull. Res. Council IsraelF9, (1960), 155-166. · Zbl 0158.25306
[5] Birkhoff, G.Lattice Theory. American Mathematical Society, Providence, R.I., (1948). · Zbl 0033.10103
[6] Blackburn, P. , de Rijke, M. and Venema,Y.Modal Logic, Cambridge University Press, (2001). · Zbl 0988.03006
[7] Blok, W.J. and van Alten, C.J. The finite embeddability property for residuated lattices, pocrims and BCK-algebras.Algebra Universalis48 (2002), 253-271. · Zbl 1058.06016
[8] Blok, W.J. and van Alten, C.J. On the finite embeddability property for residuated ordered groupoids.Transactions of AMS357, (2005), 4141-4157. · Zbl 1083.06013
[9] Blyth, T.S.Lattices and Ordered Algebraic Structures. Universitext, Springer, (2005). · Zbl 1073.06001
[10] Buszkowski, W. Some decision problems in the theory of syntactic categories. Zeitschrift f¨ur mathematische Logik und Grundlagen der Mathematik 28, 539-548, (1982). · Zbl 0499.03010
[11] Buszkowski, W. Lambek grammars based on pregroups. In: de Groote,P., Morrill, G. and Retor´e, C. (eds.), Logical Aspects of Computational Linguistics (LACL 2001), Lecture Notes in Computer Science2099, Springer, (2001), 95-109. · Zbl 0990.03021
[12] Buszkowski, W. Sequent systems for compact bilinear logic.Mathematical Logic Quarterly49, (2003), 467-474 . · Zbl 1036.03046
[13] Buszkowski, W. Lambek calculus with nonlogical axioms. In: [20], pp. 77-93.
[14] Buszkowski, W. On action logic: Equational theories of action algebras.Journal of Logic and Computation17, (2007), 199-217. · Zbl 1118.03013
[15] Buszkowski, W. Interpolation and FEP for logics of residuated algebras.Logic Journal of The IGPL19, (2011), 437-454. · Zbl 1259.03085
[16] Buszkowski, W. Some syntactic interpretations in different systems of Full Lambek Calculus. In: Ju, S. , Liu, H. and Ono, H. (eds.),Modality, Semantics and Interpretations, Logic in Asia: Studia Logica Library , Springer, (2015), 23-48. · Zbl 1429.03089
[17] Buszkowski, W. On Classical Nonassociative Lambek Calculus. In: M. Amblard, P. de Groote, S. Pogodalla and C. Retor´e (eds.), Logical Aspects of Computational Linguistics (LACL 2016), pp. 68-84, Lecture Notes in Computer Science 10054, Springer, (2016). · Zbl 1480.03011
[18] Buszkowski, W. On Involutive Nonassociative Lambek Calculus.Journal of Logic, Language and Information28, (2019), 157-181, . · Zbl 1477.03063
[19] Casadio, C., Scott, P.J. , and Seely, R.A.G. (eds.):Language and Grammar. Studies in Mathematical Linguistics and Natural Language. CSLI Publications, (2005). · Zbl 1137.03300
[20] Casadio, C. and Lambek, J. (eds.):Computational Algebraic Approaches to Natural Language. Polimetrica, (2008).
[21] Chvalovsky, K. Undecidability of consequence relation in full nonassociative Lambek calculus.Journal of Symbolic Logic80, (2015), 567-576. · Zbl 1373.03025
[22] Chvalovsky, K. and Horˇcik, R. Full Lambek Calculus with contraction is undecidable. Journal of Symbolic Logic81, (2016), 524-540. · Zbl 1355.03013
[23] Ciabattoni, A. , Galatos, N., and Terui, K. Algebraic proof theory for substructural logics: cut-elimination and completions.Annals of Pure and Applied Logic163, (2012), 266-290. · Zbl 1245.03026
[24] Coecke, B., Sadrzadeh, M. and Clark, S. Mathematical Foundations for a Compositional Distributional Model of Meaning.Linguistic Analysis36.1-4, (2010), 345-384
[25] Doˇsen, K. A brief survey of frames for the Lambek calculus.Zeitschrift f¨ur mathematische Logik und Grundlagen der Mathematik38, (1992), 179-187. · Zbl 0793.03025
[26] Ehrhard, T., Girard, J-Y., Ruet, P. and Scott, P. (eds.):Linear Logic in Computer Science. Cambridge University Press, (2004). · Zbl 1051.03003
[27] Fuchs, L.Partially Ordered Algebraic Systems. Pergamon Press, Oxford, (1963). · Zbl 0137.02001
[28] Galatos, N. and Jipsen, P. Relation algebras as expanded FL-algebras.Algebra Universalis69, (2013), 1-21. · Zbl 1322.03047
[29] Galatos, N. , Jipsen, P., Kowalski, T. and Ono, H. Residuated Lattices: An Algebraic Glimpse at Substructural Logics. Studies in Logic and The Foundations of Mathematics 151, Elsevier, (2007). · Zbl 1171.03001
[30] Galatos, N. and Ono, H. Cut elimination and strong separation for substructural logics: An algebraic approach.Annals of Pure and Applied Logic161, (2010), 1097-1133. · Zbl 1245.03027
[31] Girard, J-Y. Linear logic.Theoretical Computer Science50, (1987), 1-102 . · Zbl 0625.03037
[32] de Groote, P. and Lamarche, F. Classical non-associative Lambek calculus.Studia Logica71, (2002), 355-388. · Zbl 1032.03014
[33] H´ajek, P.Metamathematics of Fuzzy Logic.Trends in Logic, Kluwer, (1998). · Zbl 0937.03030
[34] Hoare, C. A. and Jifeng, H. The weakest prespecification I.Fundamenta Informaticae 9, (1986), 51-84. · Zbl 0603.68009
[35] Hoare, C. A. and Jifeng, H. The weakest prespecification II.Fundamenta Informaticae 9, (1986), 217-252. · Zbl 0627.68011
[36] Horˇcik, R. and K. Terui, K. Disjunction property and complexity of substructural logics.Theoretical Computer Science412, (2011), 3992-4006. · Zbl 1231.03021
[37] Hudelmaier, J. and Schroeder-Heister, P. Classical Lambek Logic. In: Baumgartner,P. R. H¨ahnle, R., and Posegga, J. (eds.),Theorem Proving with Analytic Tableaux and Related Methods, Springer, (1995), 245-262.
[38] J¨ager, G. Residuation, structural rules and context-freeness.Journal of Logic, Language and Information13, (2004), 47-59. · Zbl 1039.03018
[39] J´onsson, B. and Tsinakis, C. Relation algebras as residuated Boolean algebras.Algebra Universalis30, (1993), 469-478 · Zbl 0792.06012
[40] Kaminski, M. and Francez, N. Relational semantics of the Lambek calculus extended with classical propositional logic.Studia Logica102, (2004), 479-497. · Zbl 1322.03018
[41] Kaminski, M. and Francez, N. The Lambek calculus extended with intuitionistic propositional logic.Studia Logica104, (2016), 1051-1082. · Zbl 1417.03165
[42] Kozak, M. Distributive Full Lambek Calculus has the finite model property.Studia Logica91, (2009), 201-216. · Zbl 1183.03021
[43] Kurucz, A. N´emeti, I. , Sain, I. and Simon, A. Decidable and undecidable logics with a binary modality.Journal of Logic, Language and Information4, (1995), 191-206 . · Zbl 0840.03014
[44] Kuznetsov, S. Lambek grammars with the unit. In: de Groote, P. and Nederhof, M.-J. (eds.), Formal Grammar 2010/2011,Lecture Notes in Computer Science7395, (2012). Springer, 262-266. · Zbl 1370.03037
[45] Kuznetsov, S. The logic of action lattices is undecidable.Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science(LICS), 2019.
[46] Lafont, Y. The finite model property for various fragments of linear logic.Journal of Symbolic Logic62, (1997), 1202-1208. · Zbl 0897.03010
[47] Lambek, J. The mathematics of sentence structure.The American Mathematical Monthly65, (1958), 154-170. · Zbl 0080.00702
[48] Lambek, J. On the calculus of syntactic types. In: Jakobson, R. (ed.), Structure of Language and Its Mathematical Aspects.Proc. of Symposium in Applied Mathematics, American Mathematical Society, Providence, R.I., (1961),166-178.
[49] Lambek, J. Deductive systems and categories I.Journal of Mathematical System Theory2, (1968), 287-318. · Zbl 0176.28901
[50] Lambek, J. Cut elimination for classical bilinear logic.Fundamenta Informaticae22, (1995), 53-67. · Zbl 0817.03027
[51] Lambek, J. Some lattice models of bilinear logic.Algebra Universalis34, (1995), 541- 550. · Zbl 0840.03044
[52] Lambek, J. Type grammars revisited. In: Lecomte, A., Lamarche, F., and Perrier, G. (eds.), Logical Aspects of Computational Linguistics (LACL 1997),Lecture Notes in Computer Science1582, Springer, (1999), p 1-27. · Zbl 0934.03043
[53] Lambek, J.From Word to Sentence - a computational algebraic approach to grammar. Polimetrica, 2008. · Zbl 1166.03315
[54] Lambek, J. and Scott, P. J.Introduction to higher order categorical logic. Cambridge University Press, (1986). · Zbl 0596.03002
[55] Lin, Z. and Ma, M. On the complexity of the equational theory of residuated boolean algebras. In: J. Vaananen et al. (eds.), WoLLIC 2016,Lecture Notes in Computer Science9803, Springer, (2016), 265-278. · Zbl 1478.03083
[56] Moortgat, M. Multimodal linguistic inference. Journal of Logic, Language and Information 5, 349-385, (1996). · Zbl 0919.03023
[57] Moortgat, M. Categorial type logic. In: [76], pp. 93-177.
[58] Moortgat, M. and Oehrle, R. T. Pregroups and type-logical grammar: Searching for convergence. In: [20], 141-160.
[59] Moot, R. and Retor´e, C. The Logic of Categorial Grammars.Lecture Notes in Computer Science6850, Springer, (2012). · Zbl 1261.03001
[60] Morrill, G.Type-Logical Grammar: Categorial Logic of Signs. Kluwer, (1994). · Zbl 0848.03007
[61] Okada, M. and Terui, K. The finite model property for various fragments of intuitionistic linear logic.Journal of Symbolic Logic64, 790-802, (1999). · Zbl 0930.03021
[62] Ono, H. and Komori, Y. Logics without the contraction rule.Journal of Symbolic Logic50, (1985), 169-201. · Zbl 0583.03018
[63] Pentus, M. Lambek grammars are context-free. In:Proc. of the 8th IEEE Symposium on Logic in Computer Science, (1993), pp. 429-433.
[64] Pentus, M. Models for the Lambek calculus.Annals of Pure and Applied Logic75, (1995), 179-213. · Zbl 0829.03022
[65] Pentus, M. Lambek calculus is NP-complete.Theoretical Computer Science357, (2006), 186-201. · Zbl 1104.03013
[66] Pratt, V. Action logic and pure induction. In: van Eijck, J. (ed.), Logics in AI,Lecture Notes in Computer Science478, Springer, (1991), 97-120. · Zbl 0814.03024
[67] Preller, A. and Lambek, J. Free compact 2-categories.Mathematical Structures in Computer Science, 17, (2007), 309-340. · Zbl 1151.18007
[68] Restall, G.An Introduction to Substructural Logics. Routledge, (2000). · Zbl 1028.03018
[69] Roorda, D.Resource Logics: Proof Theoretical Investigations. PhD Thesis, University of Amsterdam, (1991).
[70] Schroeder-Heister, P. and Doˇsen, K. (eds.):Substructural Logics.Oxford Science Publications, Clarendon Press, (1993).
[71] Solias, T. Chomsky Meets Lambek.Linguistic Analysis36.1-4, (2010), 193-223.
[72] Spinks, M. and Veroff, R. Constructive logic with strong negation is a substructural logic I.Studia Logica88, (2008), 325-348. · Zbl 1145.03013
[73] Spinks, M. and Veroff, R. Constructive logic with strong negation is a substructural logic II.Studia Logica89, (2008), 401-425. · Zbl 1166.03010
[74] van Benthem, J.Language in Action: Categories, Lambdas and Dynamic Logic. Studies in Logic and The Foundations of Mathematics 130, North-Holland, (1991). · Zbl 0717.03001
[75] van Benthem, J. and ter Meulen, A. (eds.):Handbook of Logic and Language. Elsevier, The MIT Press, (1997). · Zbl 0874.03001
[76] Yetter, D. N. Quantales and (non-commutative) linear logic.Journal of Symbolic Logic 55, (1990), 41-64. · Zbl 0701.03026
[77] Zielonka, W. Weak implicational logics related to the Lambek calculus with the empty string - Gentzen versus Hilbert formalisms. In: Makinson, D. , Malinowski, J. and Wansing, H. (eds.), Towards Mathematical Philosophy,Trends in Logic28, Springer, (2009), 201-212 · Zbl 1180.03027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.