Categorial Grammars And Their Logics

3m ago
353.26 KB
28 Pages

Categorial Grammars and Their LogicsWojciech BuszkowskiAdam Mickiewicz University in PoznańPublished in: A. Garrido and U. Wybraniec-Skardowska (eds.), The LvovWarsaw School. Past and Present. Studies in Universal Logic, Birkhäuser, 2018,pp. 91–115.AbstractThis paper surveys the development of categorial grammars (also calledtype grammars) with emphasis on type logics (i.e. logical calculi underlying these grammars) and their relation to the origin in Ajdukiewicz [4].1IntroductionIn the modern literature Kazimierz Ajdukiewicz is commonly accepted as thefather of categorial grammars: formal grammars assigning logical types to expressions. His seminal paper [4] provided a clear idea of these grammars.Ajdukiewicz acknowledged an impact of E. Husserl and S. Leśniewski. FromHusserl [31] he took the idea of semantical categories which can be defined interms of mutual substitution of expressions in meaningful or sentential contexts.From Leśniewski he took a classification of categories in basic categories andfunctor categories. Here I cannot cite any single publication of S. Leśniewski,since in his works he never wrote a longer passage on this matter. Ajdukiewiczand other authors cite [45], but this paper on new foundations of mathematicsmerely contains short notes on ‘the theory of semantical categories’; differentlogical symbols are characterized as functors of a particular category (no specialsymbols for categories are introduced). It seems that more elaborated considerations only appeared in Leśniewski’s oral lectures.Ajdukiewicz introduced a system of indices for categories. This system isemployed in his procedure for verifying the ‘syntactic connexion’ of expressions. In [4] he writes: “We shall base our work here on the relevant results ofLeśniewski, adding on our part a symbolism, in principle applicable to almostall languages [and enabling us to build a calculus], which makes it possible toformally define and examine the syntactic connexion of a word pattern.”1 (Thepassage in brackets has been omitted in the English translation in [6]; I add it,since the word ‘calculus’ is quite important.) In fact, the indices for categories1 All citations from Ajdukiewicz are based on the English translations of Ajdukiewicz’soriginal papers, collected in [6].1

were introduced in Ajdukiewicz’s earlier paper [3], where they were used in asemantical analysis of the problem of universals.Let me briefly comment on terminology. The indices for categories will becalled types, according to modern standards in logic. Categories can be understood as some sets of expressions or sets of ontological objects (having acommon type). Although Leśniewski and Ajdukiewicz use the term ‘semanticalcategory’ (after Husserl), the term ‘syntactic(al) category’ is more appropriate.This was noticed by Ajdukiewicz [5]: “The concept of semantical categories mustbe clearly distinguished from the concept of syntactical categories. The term‘semantical category’ was introduced for the first time by Husserl; however, theconcept he associated with it would correspond better to the term ‘syntacticalcategory’. For Husserl pointed out that the expressions of a language may beclassified according to the role they can play within a sentence. He defined,therefore, the categories from the syntactical viewpoint.” Ajdukiewicz [5] outlined a theory of semantical categories: the type of an expression is determinedby the ontological type of the denotation of this expression. The first semanticalinterpretation of [4] is due to Bocheński [13].The connections of syntactic (semantic) types with categories defined bymutual substitution are by no way obvious, nor simple. They are quite tightfor deterministic (or: rigid) grammars which assign at most one type to oneexpression, but become less regular for categorially ambiguous grammars. Athorough discussion of this topic can be found in [19] .The present paper focuses on categorial grammars: how they developed fromthe origin in [4] to their modern forms. Categorial grammars are also called ‘typegrammars’, and the latter term seems better. The classification of expressionsin categories appears in different grammar formalisms (e.g. phrase structuregrammars), whereas logical types assigned to expressions are characteristic ofthe grammars considered here. To emphasize this Morrill [51] and others usean even more explicit term ‘type logical grammar’. In the present paper bothterms are used: the former in traditional names of grammars, the latter ingeneral considerations.The impact of [4] can be seen in several areas of formal linguistics and logical philosophy of language. Type grammars belong to formal linguistics, sincetheir main intention is to describe natural language. They are closely related totype-theoretic semantics of natural language, initiated by Monatgue [46], withan explicit reference to [4], and extensively studied by many authors as Montague Grammar. Some other works may be counted to the logical turn: theystudy types and categories in formal languages of logic and mathematics. Thisdirection was represented in Poland by Suszko [62, 63], Wybraniec-Skardowska[67] and others. Suszko elaborated a formal framework for syntax and semanticsof higher-order languages. Wybraniec-Skardowska presented a general theory of‘categorial languages’ with a distinction between expression-tokens and abstractexpressions (this theory, however, does not directly address natural language).Talasiewicz [64] provided a philosophical analysis of Ajdukiewicz’s approach,applied to natural language, with an interpretation in terms of situation semantics,2

It is a bit surprising that just the linguistic turn leads to new logical calculi (Lambek logics) and models (residuated algebras), whereas the logical turnusually focuses on some standard logical systems (higher-order logics, type theories). To keep this survey in a reasonable size I will mainly write on the newlogics elaborated for type grammars and only briefly note some links with otherdevelopments. Montague Grammar and its descendants cannot be discussed indetail; the reader is referred to [12] and the items cited there.This survey is addressed to a wide community, not necessarily experts in typegrammars. Therefore I omit mathematical subtleties. I do not even discuss allimportant mathematical results in this area; I only briefly note some of themto clarify the main ideas. Nonetheless an acquaintance with general logic andformal linguistics may help the reader to follow the text. I provide a couple oflinguistic examples, but all are quite simple. The reader is referred to [50, 49,51, 52, 44] for a more advanced linguistic material.Section 2 is concerned with basic categorial grammars, a framework directlyrelated to Ajdukiewicz’s proposal (modified in [8]). Section 3 discusses theLambek calculus and several analogous systems with a particular emphasis ontheir role in type grammars. At the end, I defend the view that Lambek logicsare important, general logics of syntactic and semantic types (besides otherapplications), but not as good for efficient parsing. An optimal strategy seemsthe following: (1) to apply Lambek logics in metatheory and on the lexical level,(2) to preserve the Ajdukiewicz system as a parsing procedure for compoundexpressions.2Basic categorial grammarsAjdukiewicz (following Leśniewski) distinguishes two basic categories: sentence(type s) and name (type n), but stipulates that in general “nothing could bedecided about the number and kind of basic semantic [categories] and functorcategories, since these may vary in different languages.” The types of functorcategories have the form of fractions:α;β1 . . . βnan expression of this type with arguments of type β1 , . . . , βn forms a compoundexpression of type α. For example, an intransitive verb is of type ns , a transitiveverb of type nsn , a sentential connective of type sss , an adverb of type αα forα ns , and so on.The procedure of checking the ‘syntactic connexion’ of a compound expression is designed as follows. First, the expression is rewritten in prefix notation:each functor directly precedes its arguments. So one writes likes John wineinstead of John likes wine and hardly works John instead of John workshardly (my examples). Second, one considers the sequence of types corresponding to the words of the rearranged expression. For these two examples3

one obtains the sequences:s, n, n andnnsnsn,s, n.nThird, one reduces a block of adjacent types:α, β1 , . . . , βnβ1 . . . βnto α and repeats this step as many times, as possible. If this reduction endsin a single type, the expression is qualified to be ‘syntactically connected’ andassigned the resulting type. The Ajdukiewicz reduction procedure applied toour examples yields:s, n, n s in one step,nnssn s, n , n s in two steps.s ,nn nSo both expressions are syntactically connected (of type s). In fact, Ajdukiewicz’soriginal procedure was more restrictive: at each step one reduces the left-mostoccurrence of a reducible pattern, but this constraint narrows its applications[17].This approach reveals two characteristic components of modern type grammars: (1) the type lexicon, i.e. an assignment of types to words, (2) the typeprocessing machinery, i.e. a procedure of checking the grammatical correctness of arbitrary expressions and at the same time deriving types of them. Interms of contemporary computational linguistics, (2) is a parsing procedure.Ajdukiewicz was the first who clearly formulated the problem of parsing andproposed a parsing algorithm (twenty years before mathematical linguistics wasfounded by Noam Chomsky).The Ajdukiewicz procedure requires the rewriting of the parsed expressionin prefix notation. In practice this restricts its applications to some formallanguages. In fact Ajdukiewicz acknowledged that one of his goals was a generalization of the parenthesis-free notation, elaborated by J. Lukasiewicz forpropositional logics, toward richer formal languages. On the other hand, his examples came from natural languages, and he expected a wide applicability of hismethod. Probably he admitted various modifications of the original procedure,when applied in practice.Bar-Hillel [7] adjusted this approach to natural language. He introduceddirectional types of the form:αβ1 . . . βm ; γ1 . . . γnand the reduction procedure based on the rule:β1 , . . . , β m ,α, γ1 , . . . , γn α.β1 . . . βm ; γ1 . . . γn4

Now transitive verbs are assigned typen,sn;n ,and John likes Mary is parsed as:s, n s in one step.n; nIn [8], this approach was modified. After Lambek [40], functor types wererestricted to α\β and α/β. An expression of type α\β (resp. β/α) with anargument of type α on the left (resp. on the right) forms a compound expressionβαin the former notation, α/β to ;β, and theof type β. So α\β corresponds to α;αfraction β;γ is represented as β\(α/γ) or (β\α)/γ. The representation of manyargument types by (nested) one-argument types is closely related to ‘currying’,i.e. the representation of many-argument functions by one-argument functionsof higher order, a routine in modern type theories.The reduction procedure is based on two rules:(RED.1) α, α\β β, (RED.2) α/β, β α .In [8], a categorial grammar is formally defined as a triple G (Σ, I, s) suchthat Σ is a nonempty finite set, I is a finite relation between elements of Σand types, and s is an atomic type. The elements of Σ are interpreted as thewords of a natural language (then Σ is referred to as the lexicon) or symbols ofa formal language (then Σ is referred to as the alphabet). Nowadays I is calledthe type lexicon or the initial type assignment. Often I is represented as a mapwhich assigns finite sets of types to elements of Σ. In examples we write v : αfor α I(v). One refers to s as the designated type. One admits an arbitraryfinite set of atomic types.Finite sequences of elements of Σ are called strings (on Σ). The empty stringis denoted by . The string (v1 , . . . , vn ) is usually written as v1 . . . vn . One saysthat G assigns type α to the string v1 . . . vn , if there exist types α1 , . . . , αn ,belonging to I(v1 ), . . . , I(vn ), respectively, such that the sequence α1 , . . . , αnreduces to α by finitely many applications of rules (RED.1), (RED.2). Thelanguage of G consists of all strings on Σ which are assigned type s by G.In the modern literature, categorial grammars in the sense of [8] are called basic categorial grammars (BCGs) or: classical categorial grammars, AB-grammars(a credit to Ajdukiewicz and Bar-Hillel).The main mathematical theorem of [8] establishes the weak equivalence ofBCGs and Chomsky’s ( free) context-free grammars (CFGs). Recall that aCFG is defined as a quadruple G (Σ, N, s, P ) such that Σ and N are disjointfinite sets (whose elements are treated as simple symbols), s N , and P is afinite set of pairs (a, x), where a N and x is a string on Σ N . The elementsof Σ (resp. N ) are called terminal symbols (resp. nonterminal symbols orvariables), and s is called the start symbol. The pairs in P are called productionrules. one writes a 7 x for (a, x) and interprets it as a rewriting rule: thestring yaz can be rewritten as yxz according to this rule (by xy one denotes theconcatenation of x and y). The language of G (or: generated by G) consists ofall strings on Σ which can be derived from s by finitely many applications ofthe production rules. A CFG is free, if it contains no nullary rule of the form5

a 7 . The equivalence theorem states that BCGs and free CFGs generatethe same class of languages. More precisely, for any BCG G there exists an free CFG G0 such that L(G) L(G0 ), and conversely.The first part of this theorem can easily be proved: a BCG G (Σ, I, s)generates the same language as the CFG with the terminal alphabet Σ, thenonterminal alphabet consisting of all types involved in G and their subtypes(i.e. subterms), the start symbol s, and the