# zbMATH — the first resource for mathematics

Logic and grammar. (English) Zbl 1283.03061
The author notes that, provided that structural rules are ignored, Gentzen’s sequents $$\Gamma\rightarrow A$$ represent context-free derivations in linguistics. More generally, a derivation $$\Gamma\rightarrow\Delta$$ stands for a rewrite rule in linguistics. Without structural rules, Gentzen’s sequential system for classical logic stands for bilinear logic, or more exactly, non-commutative classical bilinear logic. From a linguistic standpoint, juxtaposition on the right (standing for the tensor product) and that on the left (standing for its de Morgan dual) are to be identified, so that we have compact linear logic, which is called a production grammar by linguists and a semi-Thue system by mathematicians.
Some mathematically inclined linguists prefer to deal not directly with words but with types (called categories) residing in a substructural logical system or its algebraic counterpart. The basic idea of a categorial grammar is to associate with each word or a morpheme of the language one or more types, which are stored in one’s mind, and then to perform some logical or algebraic calculations on the sequence of types given by a string of words in order to check whether it is really a well-formed sentence. The author has worked on two kinds of such systems, namely, the syntactic calculus [Am. Math. Mon. 65, 154–170 (1958; Zbl 0080.00702)] and compact bilinear logic [Lect. Notes Comput. Sci. 1582, 1–27 (1999; Zbl 0934.03043); From word to sentence. A computational algebraic approach to grammar. Monza: Polimetrica (2008; Zbl 1166.03315)]. The former has its predecessors in [K. Ajdukiewicz, Stud. Philos. 1, 1–27 (1935; Zbl 0015.33702); Y. Bar-Hillel, Language and information: selected essays. Palo Alto: Addison-Wesley. 61–74 (1964); Language 29, 47–58 (1953; Zbl 0156.25402)]. It has an intriguing affinity to the semantic calculi of H. B. Curry [in: R. Jakobson (ed.), Structure of language and its mathematical aspects. Providence, R.I.: American Mathematical Society. 56–68 (1961; Zbl 0111.16102)] and R. Montague [Theoria 36 (1970), 373–398 (1971; Zbl 0243.02002)]. The latter algebraically corresponds to pregroups, for which a decision procedure is obtained in [Zbl 0934.03043], amounting to cut elimination as shown in [W. Buszkowski, Math. Log. Q. 49, No. 5, 467–474 (2003; Zbl 1036.03046)].
Then the author turns to category theory. From the author’s standpoint, “a $$2$$-category is just a categorical refinement of a production grammar.” Of possible interest in grammar are residuated and compact $$2$$-categories. Although residuated categories provide an insight into the proof theory of the syntactic calculus, it originated in the category of $$R$$-$$R$$ bimodules with $$R$$ being a ring. A ring-theoretic example of compact $$2$$-categories is the category of all $$R$$-$$R$$ bimodules finitely generated on each side with $$R$$ being a division ring.
The reader can enjoy the interplay among logic, linguistics and algebra in this paper.

##### MSC:
 03B65 Logic of natural languages 03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
Full Text:
##### References:
 [1] Ajdukiewicz, K. 1935, Die Syntaktische Konnexitàt, Studia Philosophica 1:1–27. English translation: Syntactic connection, in S. McCall (ed.), Polish Logic, Oxford, Clarendon Press, 1967. · Zbl 0015.33702 [2] Bar-Hillel Y. (1953) A quasi-arithmetical notation for syntactic description. Language 29: 47–58 · Zbl 0156.25402 · doi:10.2307/410452 [3] Bar-Hillel Y. (1964) Language and Information: Selected Essays. Palo Alto, Addison-Wesley · Zbl 0158.24102 [4] Benson D. B. (1970) Syntax and semantics, a categorical view. Information and Control 17: 145–166 · Zbl 0204.31802 · doi:10.1016/S0019-9958(70)90517-6 [5] Bhargava M., Lambek J. (1995) A rewrite system of the Western Pacific: Lounsbury’s analysis of Trobriand kinship terminology. Theoretical Linguistics 21: 241–253 · doi:10.1515/thli.1995.21.2-3.241 [6] Bourbaki N. (1948) Algèbre linéaire. Hermann, Paris · Zbl 0039.25902 [7] Brame, M. 1984, 1985, 1987, Recursive categorical syntax and morphology I, II, III, Linguistic Analysis 14,15,17. [8] Buszkowski, W. 2001, Lambek grammars based on pregroups, in P. G. De Groote et al. (eds.), Logical aspects of computational linguistics, LNAI 2099, Berlin, Springer. · Zbl 0990.03021 [9] Buszkowski, W. 2002, Cut elimination for the Lambek calculus of adjoints, in V. M. Abrusci et al. (eds.), New perspectives in logic and formal linguistics, Rome, Bulzoni. [10] Casadio C., Lambek J. (2002) A tale of four grammars. Studia Logica 71: 315–329 · Zbl 1011.03016 · doi:10.1023/A:1020564714107 [11] Chomsky N. (1957) Syntactic Structures. Mouton, The Hague [12] Chomsky N. (1980) Rules and representations. Columbia University Press, New York [13] Curry, H. B. 1961, Some logical aspects of grammatical structure, in R. Jacobson (ed.), Structure of language and its mathematical aspects, Providence, R.I., AMS. [14] Francez N., Kaminski M. (2007) Commutation-Augmented Pregroup Grammars and Mildly Context-Sensitive Languages. Studia Logica 87: 295–321 · Zbl 1128.68045 · doi:10.1007/s11225-007-9088-z [15] Girard J.-Y. (1987) Linear logic. Theoretical Computer Science 50: 1–102 · Zbl 0625.03037 · doi:10.1016/0304-3975(87)90045-4 [16] Harris Z. S. (1966) A cyclic cancellation automaton for sentence well-formedness. International Computation Centre Bulletin 5: 69–94 [17] Harris Z. S. (1968) Mathematical structure of language. John Wiley and Sons, New York · Zbl 0195.02202 [18] Kobele, G. M. 2008, Agreement bottlenecks in Italian, in C. Casadio et al. (eds.), Computational algebraic approaches to natural languages, Milan, Polimetrica. [19] Kusalik, T. 2008, Product pregroups as an alternative to inflectors, in C. Casadio et al. (eds.), Computational algebraic approaches to natural languages, Milan, Polimetrica. [20] Lambek J. (1958) The mathematics of sentence structure. American Mathematical Monthly 65: 154–170 · Zbl 0080.00702 · doi:10.2307/2310058 [21] Lambek, J. 1999a, Deductive systems and categories in linguistics, in H. J. Ohlbach et al. (eds.), Logic, Language and Reasoning, Dordrecht, Kluwer. · Zbl 0960.03022 [22] Lambek, J. 1999b, Type grammar revisited, in Lecomte et al. (eds.), Logical aspects of computational linguistics LNCS/LNAI 1582, Berlin, Springer. · Zbl 0934.03043 [23] Lambek, J. 2004, Bicategories in algebra and linguistics, in T. Ehrhard et al. (eds.), Linear logic in computer science, London Mathematical Society Lecture Notes Series 316, Cambridge University Press. · Zbl 1059.03083 [24] Lambek J. (2008) From word to sentence. Polimetrica, Milan · Zbl 1166.03315 [25] Lambek J. (2010) Exploring feature agreement in French with parallel pregroup computations. Journal of Logic, Language and Information 19: 75–88 · Zbl 1183.91158 · doi:10.1007/s10849-009-9098-5 [26] Lambek, J., and N. S. Yanofsky 2008, A computational approach to Biblical Hebrew, in C. Casadio et al. (eds.), Computational algebraic approaches to natural languages, Milan, Polimetrica. [27] Lawvere, F. W., Toposes, Algebraic Geometry and Logic, Lecture Note in Mathematics 274, New York, Springer. [28] Miller G. A. (1956) The magical number seven plus or minus two. Psychological Review 63: 81–97 · doi:10.1037/h0043158 [29] Mac Lane S. (1971) Categories for the working mathematician. Springer, New York · Zbl 0232.18001 [30] Montague R. (1974) Formal Philosophy: Selected Papers. Yale University Press, New Haven [31] Moortgat M. (1988) Categorial Investigations. Foris, Dordrecht [32] Moortgat, M. 1997, Categorial type logics, in J. van Benthem et al. (eds.), Handbook of Logic and Language, Amsterdam, Elsevier. [33] Pentus, M. 1993, Lambek grammars are context free, in Proceedings of the 8th annual symposium of logic in Computer Science, pp. 429–433. [34] Preller A. (2010) Polynomial pregroup grammars pursue context sensitive languages. Linguistic Analysis 36: 483 [35] Stabler, E. P. 2008, Tupled pregroup grammars, in C. Casadio et al. (eds.), Computational algebraic approaches to natural languages, Milan, Polimetrica.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.