Logic and grammar (Q692192)

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 [\textit{K. Ajdukiewicz}, Stud. Philos. 1, 1--27 (1935; Zbl 0015.33702); \textit{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 \textit{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 \textit{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 [\textit{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.