The Lambek-Grishin calculus is a symmetric version of categorialgrammar obtained by augmenting the standard inventory of type-forming operations (product and residual left and right division) with a dual family: coproduct, left and right difference. Interaction between these two families is provided by distributivity laws. These distributivity laws have pleasant invariance properties: stability of interpretations for the Curry-Howard derivational semantics, and structure-preservation at the syntactic end. The move to symmetry thus offers novel ways of reconciling the demands of (...) natural language form and meaning. (shrink)
Even though residuation is at the core of CategorialGrammar (Lambek, 1958), it is not always immediate to realize how standard logical systems like Multi-modal Categorial Type Logics (MCTL) (Moortgat, 1997) actually embody this property. In this paper, we focus on the basic system NL (Lambek, 1961) and its extension with unary modalities NL() (Moortgat, 1996), and we spell things out by means of Display Calculi (DC) (Belnap, 1982; Goré, 1998). The use of structural operators in DC (...) permits a sharp distinction between the core properties we want to impose on the logical system and the way these properties are projected into the logical operators. We will show how we can obtain Lambek residuated triple \, / and of binary operators, and how the operators and introduced by Moortgat (1996) are indeed their unary counterpart.In the second part of the paper we turn to other important algebraic properties which are usually investigated in conjunction with residuation (Birkhoff, 1967): Galois and dual Galois connections. Again, DC let us readily define logical calculi capturing them. We also provide preliminary ideas on how to use these new operators when modeling linguistic phenomena. (shrink)
We present a new axiomatization of the non-associative Lambek calculus. We prove that it takes polynomial time to reduce any non-associative Lambek categorialgrammar to an equivalent context-free grammar. Since it is possible to recognize a sentence generated by a context-free grammar in polynomial time, this proves that a sentence generated by any non-associative Lambek categorialgrammar can be recognized in polynomial time.
This article summarizes the main ideas for formalizing categorial languages genrated by classical categorialgrammar originated by K. Ajdukiewicz [1935,1960].This formalization is presented in detail in the author's monographs in Polish "Teorie Języków Syntaktycznie Kategorialnych" ("Theories of Syntactically Categorical Languages"), PWN, Warszawa-Wrocław 1985 and in English "Theory of Language Syntax, Categorial Approach", Kluwer Academic Publishers, Boston-London-Dordrecht 1991.
The paper proposes a semantics for contextual (i.e., Temporal and Locative) Prepositional Phrases (CPPs) like during every meeting, in the garden, when Harry met Sally and where I’m calling from. The semantics is embodied in a multi-modal extension of Combinatory Categoral Grammar (CCG). The grammar allows the strictly monotonic compositional derivation of multiple correct interpretations for “stacked” or multiple CPPs, including interpretations whose scope relations are not what would be expected on standard assumptions about surfacesyntactic command and monotonic (...) derivation. A type-hierarchy of functional modalities plays a crucial role in the specification of the fragment. (shrink)
Abstract -/- Quantifier domain restriction (QDR) and two versions of nominal restriction (NR) are implemented as restrictions that depend on a previously introduced interpreter and interpretation time in a two-dimensional semantic framework on the basis of simple type theory and categorialgrammar. Against Stanley (2002) it is argued that a suitable version of QDR can deal with superlatives like tallest. However, it is shown that NR is needed to account for utterances when the speaker intends to convey different (...) restrictions for multiple uses of the same quantifying determiner. We argue that NR generally fares better with such examples but also observe that examples like Every sailor waves at every sailor might be pragmatically anomalous. An account of contextual domain restriction is proposed that (i) excludes these anomalous readings (but it is shown how they could be included), (ii) makes it possible to express different contextual domain restrictions as long-range dependencies on an interpreter and an interpretation time, and (iii) additionally models restrictions based on locative constructions as general mereological constraints introduced by shifting the index. (shrink)
This paper introduces λ-grammar, a form of categorialgrammar that has much in common with LFG. Like other forms of categorialgrammar, λ-grammars are multi-dimensional and their components are combined in a strictly parallel fashion. Grammatical representations are combined with the help of linear combinators, closed pure λ-terms in which each abstractor binds exactly one variable. Mathematically this is equivalent to employing linear logic, in use in LFG for semantic composition, but the method seems more (...) practicable. (shrink)
We describe a categorial system (PPTS) based on partial proof trees(PPTs) as the building blocks of the system. The PPTs are obtained byunfolding the arguments of the type that would be associated with a lexicalitem in a simple categorialgrammar. The PPTs are the basic types in thesystem and a derivation proceeds by combining PPTs together. We describe theconstruction of the finite set of basic PPTs and the operations forcombining them. PPTS can be viewed as a (...) class='Hi'>categorial system incorporating someof the key insights of lexicalized tree adjoining grammar, namely the notionof an extended domain of locality and the consequent factoring of recursionfrom the domain of dependencies. PPTS therefore inherits the linguistic andcomputational properties of that system, and so can be viewed as a middleground between a categorialgrammar and a phrase structure grammar. We alsodiscuss the relationship between PPTS, natural deduction, and linear logicproof-nets, and argue that natural deduction rather than a proof-net systemis more appropriate for the construction of the PPTs. We also discuss howthe use of PPTs allows us to localize the management of resources, therebyfreeing us from this management as the PPTs are combined. (shrink)
Discontinuity refers to the character of many natural language constructions wherein signs differ markedly in their prosodic and semantic forms. As such it presents interesting demands on monostratal computational formalisms which aspire to descriptive adequacy. Pied piping, in particular, is argued by Pollard (1988) to motivate phrase structure-style feature percolation. In the context of categorialgrammar, Bach (1981, 1984), Moortgat (1988, 1990, 1991) and others have sought to provide categorial operators suited to discontinuity. These attempts encounter certain (...) difficulties with respect to model theory and/or proof theory, difficulties which the current proposals are intended to resolve.Lambek calculus is complete for interpretation byresiduation with respect to the adjunction operation of groupoid algebras (Buszkowski 1986). In Moortgat and Morrill (1991) it is shown how to give calculi for families of categorial operators, each defined by residuation with respect to an operation of prosodic adjunction (associative, non-associative, or with interactive axioms). The present paper treats discontinuity in this way, by residuation with respect to three adjunctions: + (associative), (.,.) (split-point marking), andW (wrapping) related by the equations 1+s 2+s 3=(s 1,s 3)Ws 2. We show how the resulting methods apply to discontinuous functors, quantifier scope and quantifier scope ambiguity, pied piping, and subject and object antecedent reflexivisation. (shrink)
We present a geometrical analysis of the principles that lay at the basis of CategorialGrammar and of the Lambek Calculus. In Abrusci it is shown that the basic properties known as Residuation laws can be characterized in the framework of Cyclic Multiplicative Linear Logic, a purely non-commutative fragment of Linear Logic. We present a summary of this result and, pursuing this line of investigation, we analyze a well-known set of categorialgrammar laws: Monotonicity, Application, Expansion, (...) Type-raising, Composition, Geach laws and Switching laws. (shrink)
Geach’s rich paper ‘A Program for Syntax’ introduced many ideas into the arena of categorialgrammar, not all of which have been given the attention they warrant in the thirty years since its first publication. Rather surprisingly, one of our findings (Section 3 below) is that the paper not only does not contain a statement of what has widely come to be known as “Geach’s Rule”, but in fact presents considerations which are inimical to the adoption of the (...) rule in question. With regard to at least some amongst the numerous other points extracted here from Geach’s discussion, we shall not be able to reach so definitive a conclusion, and content ourselves with giving the issues an airing. (shrink)
This paper studies the relation between some extensions of the non-associative Lambek Calculus NL and their interpretation in tree models (free groupoids). We give various examples of sequents that are valid in tree models, but not derivable in NL. We argue why tree models may not be axiomatizable if we add finitely many derivation rules to NL, and proceed to consider labeled calculi instead.We define two labeled categorial calculi, and prove soundness and completeness for interpretations that are almost the (...) intended one, namely for tree models where some branches of some trees may be resp. all branches of all trees must be infinitely extending. Extrapolating from the experiences in our quite simple systems, we briefly discuss some problems involved with the introduction of labels in categorialgrammar, and argue that many of the basic questions are not yet understood. (shrink)
In this paper it is shown how simple texts that can be parsed in a Lambek CategorialGrammar can also automatically be provided with a semantics in the form of a Discourse Representation Structure in the sense of Kamp . The assignment of meanings to texts uses the Curry-Howard-Van Benthem correspondence.
The article presents the first results we have obtained studying natural reasoning from a proof-theoretic perspective. In particular we focus our attention on monotonic reasoning. Our system consists of two parts: (i) A Formal Grammar – a multimodal version of classical CategorialGrammar – which while syntactically analysing linguistic expressions given as input, computes semantic information (In particular information about the monotonicity properties of the components of the input string are displayed.); (ii) A simple Natural Logic which (...) derives (monotonicity) inferences using as vehicle the parsed output. The monotonicity markers assigned in the lexicon are propagated through the proofs via a combination of the structural and the logical rules for the unary operators of Multimodal CategorialGrammar (MMCG) [Moo97]. We have chosen to work with an expressive ‘grammar logic’, in order to avoid the use of extra-logical marking devices and extra-logical structural reasoning. Having MMCG as parser, our system is able to make the derivations simply within the logic. This new approach makes the implementation of the theory an easier task. We have implemented the theoretical results, so far obtained, using Grail, a theorem prover for CategorialGrammar Logics [Moo98]. (shrink)
. Recently renewed interest in non transformational approaches to syntax  suggests that it might be well to take another look at categorial grammars, since they seem to have been neglected largely because they had been shown to be equivalent to context free phrase structure grammars in weak generative capacity and it was believed that such grammars were incapable of describing natural languages in a natural way. It is my purpose here to sketch a theory of grammar which (...) represents a generalization of categorial grammars of the sort invented by Ajdukiewicz (1935) and further elaborated especially by Bar Hillel (1953) and Lambek (1961). (shrink)
The ‘syntax’ and ‘combinatorics’ of my title are what Curry (1961) referred to as phenogrammatics and tectogrammatics respectively. Tectogrammatics is concerned with the abstract combinatorial structure of the grammar and directly informs semantics, while phenogrammatics deals with concrete operations on syntactic data structures such as trees or strings. In a series of previous papers (Muskens, 2001a; Muskens, 2001b; Muskens, 2003) I have argued for an architecture of the grammar in which ﬁnite sequences of lambda terms are the basic (...) data structures, pairs of terms syntax, semantics for example. These sequences then combine with the help of simple generalizations of the usual abstraction and application operations. This theory, which I call Lambda Grammars and which is closely related to the independently formulated theory of Abstract Categorial Grammars (de Groote, 2001; de Groote, 2002), in fact is an implementation of Curry’s ideas: the level of tectogrammar is encoded by the sequences of lambda-terms and their ways of combination, while the syntactic terms in those sequences constitute the phenogrammatical level. In de Groote’s formulation of the theory, tectogrammar is the level of abstract terms, while phenogrammar is the level of object terms. (shrink)
The distinction between COMPLEMENTS and ADJUNCTS has a long tradition in grammatical theory, and it is also included in some way or other in most current formal linguistic theories. But it is a highly vexed distinction for several reasons, one of which is that no diagnostic criteria have emerged that will reliably distinguish adjuncts from complements in all cases — too many examples seem to fall into the crack between the two categories, no matter how theorists wrestle with them.
In this paper the notion of unifier is extended to the infinite set case. The proof of existence of the most general unifier of any infinite, unifiable set of types (terms) is presented. Learning procedure, based on infinite set unification, is described.
This paper gives a simple method for providing categorial brands of feature-based unification grammars with a model-theoretic semantics. The key idea is to apply the paradigm of fibred semantics (or layered logics, see Gabbay (1990)) in order to combine the two components of a feature-based grammar logic. We demonstrate the method for the augmentation of Lambek categorialgrammar with Kasper/Rounds-style feature logic. These are combined by replacing (or annotating) atomic formulas of the first logic, i.e. the (...) basic syntactic types, by formulas of the second. Modelling such a combined logic is less trivial than one might expect. The direct application of the fibred semantics method where a combined atomic formula like np (num: sg & pers: 3rd) denotes those strings which have the indicated property and the categorial operators denote the usual left- and right-residuals of these string sets, does not match the intuitive, unification-based proof theory. Unification implements a global bookkeeping with respect to a proof whereas the direct fibring method restricts its view to the atoms of the grammar logic. The solution is to interpret the (embedded) feature terms as global feature constraints while maintaining the same kind of fibred structures. For this adjusted semantics, the anticipated proof system is sound and complete. (shrink)
This book presents a formal and philosophical analysis of language syntax. It refers to some ideas of E.Husserl and G. Frege, to S. Leśniewski's theory of syntactic categories and K. Ajdukiewicz's conception of formal grammar, also to Ch.S. Pierces's distinction between tokens (concrete linguistic entities) and types (ideal linguistic entities) and to A.A. Markov's theory of algorithms. The central aim of the book is - in the spirit of these ideas - to provide both strict yet comprehensive lectures on (...) two axiomatic theories of languages (grammars) irrespective of specific structure of their expression and the notation used in them. The main feature of these theories are that definitions of well-formed expression allow the formulation of algorithms for the examination of syntactic correctness of expressions and that their formalizations are bi-level, in reference to opposite philosophical orientations: nominalistic and idealistic. The theoretical considerations in the book speak in favour of the former. The book contains a translation of the basic contents of the book in Polish "Teorie języków syntaktycznie kategorialnych ("Theories of syntactically categorial languages"), PWN, Warszawa-Wrocław 1985, and extensive Introduction and Final Remarks. In Introduction are discussed the main assumptions, objectives and conditionings of presented theories and intuitive foundations of these theories. Final Remarks are connected with the subject-matter of the book and the ability to build syntax theories in the opposition spirit, because of the Platonic approach to language syntax. -/- . (shrink)
Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string (...) and tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)
It is proved that for any k, the class of classical categorial grammars that assign at most k types to each symbol in the alphabet is learnable, in the Gold (1967) sense of identification in the limit from positive data. The proof crucially relies on the fact that the concept known as finite elasticity in the inductive inference literature is preserved under the inverse image of a finite-valued relation. The learning algorithm presented here incorporates Buszkowski and Penn's (1990) algorithm (...) for determining categorial grammars from input consisting of functor-argument structures. (shrink)
Right-node raising of anaphors and bound pronouns out of coordinations, as in "Every student likes, and every professor hates, himself / his neighbors" is judged more acceptable in German and Dutch than in English. Using combinatory categorialgrammar, this paper ties the cross-linguistic difference to the fact that German and Dutch are V-2 languages, and V-2 necessitates a lifted category for verbs that automatically caters to the right-node raised duplicator. The same lifted category is optionally available in English, (...) but it is not needed for independent syntactic purposes. (shrink)
Two axiomatizations of the nonassociative and commutative Lambek syntactic calculus are given and their equivalence is proved. The first axiomatization employs Permutation as the only structural rule, the second one, with no Permutation rule, employs only unidirectional types. It is also shown that in the case of the Ajdukiewicz calculus an analogous equivalence is valid only in the case of a restricted set of formulas. Unidirectional axiomatizations are employed in order to establish the generative power of categorial grammars based (...) on the nonassociative and commutative Lambek calculus with product. Those grammars produce CF-languages of finite degree generated by CF-grammars closed with respect to permutations. (shrink)
Grammar can be formulated as a kind of substructural propositional logic. In support of this claim, we survey bare Gentzen style deductive systems and two kinds of non-commutative linear logic: intuitionistic and compact bilinear logic. We also glance at their categorical refinements.