Type logics and pregroups. (English) Zbl 1134.03014
The author first outlines several type logics related to the Lambek calculus L as well as their semantical frameworks by linguistic and algebraic means, among them the logic of pregroups, or Compact Bilinear Logic CBL, which is the primary subject of the paper. The main issue is a formalization of an extended sequent system of CBL enjoying the cut-elimination theorem and the normalization theorem (corresponding to the Lambek switching lemma for CBL), with which are obtained the P-TIME decidability (for CBL and the extension) and a faithful interpretation of CBL in L1 (L with the unitary constant 1). The author also surveys the results on pregroups he has established so far, and provides a general construction of (preordered) bilinear algebras and pregroups whose universe is an arbitrary monoid.
Reviewer: Osamu Sonobe (Follonica)
MSC:
| 03B47 | Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) |
| 03B65 | Logic of natural languages |
| 03F05 | Cut-elimination and normal-form theorems |
Keywords:
bilinear algebra; pregroup; Lambek calculus; substructural logics; type logic; categorial grammarReferences:
| [1] | Abrusci V.M., (1991) ’Phase semantics and sequent system for pure noncommutative classical propositional logic’. Journal of Symbolic Logic 56:1403–1454 · Zbl 0746.03044 · doi:10.2307/2275485 |
| [2] | Ajdukiewicz K., (1935) ’Die syntaktische Konnexität’. Studia Philosophica 1:1–27 · JFM 62.1050.03 |
| [3] | Bar-Hillel Y., Gaifman C., Shamir E. (1960) ’On categorial and phrase structure grammars’. Bull. Res Council Israel F9:155–166 · Zbl 0158.25306 |
| [4] | Béchet, D., ’Parsing Pregroup Grammars and the Lambek Calculus using Partial Composition’, this issue. · Zbl 1133.03011 |
| [5] | van Benthem J., (1986) Essays in Logical Semantics. D. Reidel, Dordrecht |
| [6] | van Benthem J., (1991) Language in Action. Categories, Lambdas and Dynamic Logic. North-Holland, Amsterdam · Zbl 0717.03001 |
| [7] | van Benthem J., (1996) Exploring Logical Dynamics. CSLI, Stanford · Zbl 0873.03001 |
| [8] | van Benthem J., Ter Meulen A. (eds) (1997) Handbook of Logic and Language. Elsevier, Amsterdam · Zbl 0874.03001 |
| [9] | Bulińska, M., ’P-TIME Decidabilty of NL1 with Assumptions’, Electronic Proc. Formal Grammars 2006, 29–38. |
| [10] | Buszkowski W., (1982) ’Some decision problems in the theory of syntactic categories’. Zeitschrift f. math. Logik und Grundlagen d. Math. 28:539–548 · Zbl 0499.03010 · doi:10.1002/malq.19820283308 |
| [11] | Buszkowski W., (1986) ’Completeness results for Lambek Syntactic Calculus’. Zeitschrift f. math. Logik und Grundlagen d. Math. 32:13–28 · Zbl 0594.03015 · doi:10.1002/malq.19860320104 |
| [12] | Buszkowski W., (1986) ’Generative Capacity of Non-Associative Lambek Calculus’. Bulletin of Polish Academy of Sciences. Math. 34:507–516 · Zbl 0618.03013 |
| [13] | Buszkowski, W., ’Generative Power of Categorial Grammars’, [40]:69–94. · Zbl 0636.03020 |
| [14] | Buszkowski, W., ’Lambek Grammars Based on Pregroups’, [24]:95–109. · Zbl 0990.03021 |
| [15] | Buszkowski W., (2002) ’Pregroups: Models and Grammars’. Relational Methods in Computer Science, LNCS 2561:35–49 · Zbl 1027.68069 · doi:10.1007/3-540-36280-0_3 |
| [16] | Buszkowski W., (2003) ’Sequent Systems for Compact Bilinear Logic’. Mathematical Logic Quarterly, 49:467–474 · Zbl 1036.03046 · doi:10.1002/malq.200310050 |
| [17] | Buszkowski, W., ’Lambek Calculus with Non-Logical Axioms’, [19]:77–93. |
| [18] | Buszkowski W., (2007) ’On Action Logic: Equational Theories of Action Algebras’. Journal of Logic and Computation 17.1:199–217 · Zbl 1118.03013 |
| [19] | Casadio, C., P.J. Scott, and R. Seely (eds.), Language and Grammar. Studies in Mathematical Linguistics and Natural Language, CSLI Lecture Notes 168, Stanford, 2005. · Zbl 1137.03300 |
| [20] | Fadda, M., ’Towards flexible pregroup grammars’, New Perspectives in Logic and Formal Linguistics, 95–112, Bulzoni Editore, Roma, 2002. |
| [21] | Farulewski, M., ’Finite Embeddability Property of Residuated Ordered Groupoids’, Reports on Mathematical Logic. To appear. · Zbl 1156.06006 |
| [22] | Francez, N. and M. Kaminski, ’Commutation-Augmented Pregroup Grammars and Mildly Context-Sensitive Languages’, this issue. · Zbl 1128.68045 |
| [23] | Girard J.-Y., (1987) ’Linear logics’. Theoretical Computer Science 50:1–102 · Zbl 0625.03037 · doi:10.1016/0304-3975(87)90045-4 |
| [24] | de Groote, P., G. Morrill, and C. Retoré (eds.), Logical Aspects of Computational Linguistics, LNAI 2099, Springer, 2001. |
| [25] | Jäger G., (2004) ’Residuation, structural rules and context-freeness’. Journal of Logic, Language and Information 13:47–59 · Zbl 1039.03018 · doi:10.1023/A:1026175817625 |
| [26] | Jipsen P., (2004) ’From Semirings to Residuated Kleene Algebras’. Studia Logica 76:291–303 · Zbl 1045.03049 · doi:10.1023/B:STUD.0000032089.54776.63 |
| [27] | Kanazawa M., (1992) ’The Lambek Calculus Enriched with Additional Connectives’. Journal of Logic, Language and Information 1.2:141–171 · Zbl 0793.03028 · doi:10.1007/BF00171695 |
| [28] | Kandulski M., (1988) ’The equivalence of nonassociative Lambek categorial grammars and context-free grammars’. Zeitschrift f. math. Logik und Grundlagen d. Math. 34:41–52 · Zbl 0655.03017 · doi:10.1002/malq.19880340106 |
| [29] | Kandulski M., (1993) ’Normal Form of Derivations for the Nonassociative and Commutative Lambek Calculus with Product’. Mathematical Logic Quarterly 39:103–114 · Zbl 0803.03015 · doi:10.1002/malq.19930390113 |
| [30] | Kiślak-Malinowska, A., ’On the logic of {\(\beta\)} pregroups’, this issue. · Zbl 1138.03021 |
| [31] | Lambek J., (1958) ’The mathematics of sentence structure’. American Mathematical Monthly 65:154–170 · Zbl 0080.00702 · doi:10.2307/2310058 |
| [32] | Lambek J., ’On the calculus of syntactic types’, Structure of Language and Its Mathematical Aspects. Proc. Symp. Appl. Math., AMS, Providence, 166–178, 1961 |
| [33] | Lambek, J., ’From categorial grammar to bilinear logic’, [47]:207–237. · Zbl 0941.03518 |
| [34] | Lambek, J., ’Type Grammars Revisited’, [37]:1–27. · Zbl 0934.03043 |
| [35] | Lambek J., (2001) ’Type Grammars as Pregroups’. Grammars 4:21–39 · Zbl 1007.03031 · doi:10.1023/A:1011444711686 |
| [36] | Lambek, J., ’Should Pregroup Grammars be Adorned with Additional Operations?’, this issue. · Zbl 1155.03013 |
| [37] | Lecomte, A., F. Lamarche, and G. Perrier (eds.), Logical Aspects of Computational Linguistics, LNAI 1582, Springer, 1999. |
| [38] | Moortgat, M., ’Categorial Type Logic’, [8]:93–177. |
| [39] | Morrill G., (1994) Type Logical Grammar. Kluwer, Dordrecht · Zbl 0848.03007 |
| [40] | Oehrle, R. T., E. Bach, and D. Wheeler (eds.), Categorial Grammars and Natural Language Structures, D. Reidel, Dordrecht, 1988. |
| [41] | Ono, H., ’Semantics of Substructural Logics’, [47]:259–291. · Zbl 0941.03522 |
| [42] | Pentus, M., ’Lambek Grammars are Context-Free’, Proc. 8th IEEE Symp. Logic in Computer Scie., 429–433, 1993. |
| [43] | Pentus M., (1995) ’Models for the Lambek Calculus’. Annals of Pure and Applied Logic 75:179–213 · Zbl 0829.03022 · doi:10.1016/0168-0072(94)00063-9 |
| [44] | Pentus M., (2006) ’Lambek calculus is NP-complete’. Theoretical Computer Science 357:186–201 · Zbl 1104.03013 · doi:10.1016/j.tcs.2006.03.018 |
| [45] | Preller, A., ’Category Theoretical Semantics for Pregroup Grammars’, Logical Aspects of Computational Linguistics, LNAI 3492, Springer, Berlin, 2005, pp. 254–270. · Zbl 1082.68045 |
| [46] | Preller A., Lambek J., (2007) ’Free compact 2-categories’. Mathematical Structures in Computer Science 17:309–340 · Zbl 1151.18007 · doi:10.1017/S0960129506005901 |
| [47] | Schroeder-Heister P., Dosen K. (eds) (1993) Substructural Logics. Clarendon Press, Oxford · Zbl 0840.03011 |
| [48] | Yetter D.N. (1990) ’Quantales and (Non-Commutative) Linear Logic’. Journal of Symbolic Logic 55:41-64 · Zbl 0701.03026 · doi:10.2307/2274953 |
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.
