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)

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 finite 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)

What is the meaning of language expressions and how to compute or calculate it? In this paper, we give an answer to this question by analysing the meanings of aspects and tenses in natural languages inside the formal model of an grammar of applicative, cognitive and enunciative operations , using the applicative formalism, functional types of categorial grammars and combinatory logic . In the enunciative theory and following , an utterance can be decomposed into two components: a (...) modus and a dictum . In GRACE, the modus is a complex operator applied to a proposition and is generated from more elementary operators of the categories of tense, aspect, and modality. The dictum is a proposition generated by a predicative relation. In this way, we can attribute a semantic meaning to different grammatical aspecto-temporal operators. The applicative expressions of CL can be easily translated into a functional programming language such as HASKELL or CAML. (shrink)

The Lambek-Grishin calculus is a symmetric version of categorial grammar 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)

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 categorial grammar, 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)

In this paper it is shown how simple texts that can be parsed in a Lambek Categorial Grammar can also automatically be provided with a semantics in the form of a Discourse Representation Structure in the sense of Kamp [1981]. The assignment of meanings to texts uses the Curry-Howard-Van Benthem correspondence.

This paper argues that the faculty of language comes essentially for free in evolutionary terms, by grace of a capacity shared with some evolutionarily quite distantly related animals for deliberatively planning action in the world. The reason humans have language of a kind that animals do not is because of a qualitative difference in the nature of human plans rather than anything unique to language.

We provide an algorithm for determining a categorial grammar from linguistic data that essentially uses unification of type-schemes assigned to atoms. The algorithm presented here extends an earlier one restricted to rigid categorial grammars, introduced in [4] and [5], by admitting non-rigid outputs. The key innovation is the notion of an optimal unifier, a natural generalization of that of a most general unifier.

This paper introduces λ-grammar, a form of categorial grammar that has much in common with LFG. Like other forms of categorial grammar, λ-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)

For the most part, the papers collected in this volume stern from presentations given at a conference held in Tucson over the weekend of May 31 through June 2, 1985. We wish to record our gratitude to the participants in that conference, as well as to the National Science Foundation and the University of Arizona SBS Research Institute for their financial support. The advice we received from Susan Steele on organizational matters proved invaluable and had many felicitous consequences for the (...) success of the con­ ference. We also would like to thank the staff of the Departments of Linguistics of the University of Arizona and the University of Massachusetts at Amherst for their help, as weIl as a number of individuals, including Lin Hall, Kathy Todd, and Jiazhen Hu, Sandra Fulmer, Maria Sandoval, Natsuko Tsujimura, Stuart Davis, Mark Lewis, Robin Schafer, Shi Zhang, Olivia Oehrle-Steele, and Paul Saka. Finally, we would like to express our gratitude to Martin Scrivener, our editor, for his patience and his encouragement. Vll INTRODUCTION The term 'categorial grammar' was introduced by Bar-Rillel as a handy way of grouping together some of his own earlier work and the work of the Polish logicians and philosophers Lesniewski and Ajdukiewicz, in contrast to approaches to linguistic analysis based on phrase structure grammars. (shrink)

1 Recognition Device . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Classical Categorial Grammar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 (...) 3 Classical Categorial Grammar. Examples . . . . . . . . . . . . . . . . . . . . . 5 4 Logic Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5 Lambek calculus. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6 Lambek calculus. Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7 Lambek calculus. Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 8 Derivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 9 Residuated and Galois Connected Functions . . . . . . . . . . . . . . . . . . 14 10 Interpretation of the Constants. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 11 Nonveridical Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 12 Dutch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 13 Classification of NPIs in Dutch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 14 Antilicensing Relation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.. (shrink)

To model behavioral and neural correlates of language comprehension in naturalistic environments, researchers have turned to broad‐coverage tools from natural‐language processing and machine learning. Where syntactic structure is explicitly modeled, prior work has relied predominantly on context‐free grammars (CFGs), yet such formalisms are not sufficiently expressive for human languages. Combinatory categorial grammars (CCGs) are sufficiently expressive directly compositional models of grammar with flexible constituency that affords incremental interpretation. In this work, we evaluate whether a more expressive CCG (...) provides a better model than a CFG for human neural signals collected with functional magnetic resonance imaging (fMRI) while participants listen to an audiobook story. We further test between variants of CCG that differ in how they handle optional adjuncts. These evaluations are carried out against a baseline that includes estimates of next‐word predictability from a transformer neural network language model. Such a comparison reveals unique contributions of CCG structure‐building predominantly in the left posterior temporal lobe: CCG‐derived measures offer a superior fit to neural signals compared to those derived from a CFG. These effects are spatially distinct from bilateral superior temporal effects that are unique to predictability. Neural effects for structure‐building are thus separable from predictability during naturalistic listening, and those effects are best characterized by a grammar whose expressive power is motivated on independent linguistic grounds. (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)

Even though residuation is at the core of Categorial Grammar (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 categorial grammar 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 categorial grammar can be recognized in polynomial time.

[1]. Recently renewed interest in non transformational approaches to syntax [2] 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)

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 categorial grammar, 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)

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 categorial grammar, and argue that many of the basic questions are not yet understood. (shrink)

The equivalence of (classical) categorial grammars and context-free grammars, proved by Gaifman [4], is a very basic result of the theory of formal grammars (an essentially equivalent result is known as the Greibach normal form theorem [1], [14]). We analyse the contents of Gaifman's theorem within the framework of structure and type transformations. We give a new proof of this theorem which relies on the algebra of phrase structures and exhibit a possibility to justify the key construction used in (...) Gaifman's proof by means of the Lambek calculus of syntactic types [15]. (shrink)

Geach’s rich paper ‘A Program for Syntax’ introduced many ideas into the arena of categorial grammar, 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)

We present a general theory of scope and binding in which both crossover and superiority violations are ruled out by one key assumption: that natural language expressions are normally evaluated (processed) from left to right. Our theory is an extension of Shan’s (2002) account of multiple-wh questions, combining continuations (Barker, 2002) and dynamic type-shifting. Like other continuation-based analyses, but unlike most other treatments of crossover or superiority, our analysis is directly compositional (in the sense of, e.g., Jacobson, 1999). In particular, (...) it does not postulate a level of Logical Form or any other representation distinct from surface syntax. One advantage of using continuations is that they are the standard tool for modeling order-of-evaluation in programming languages. This provides us with a natural and independently motivated characterization of what it means to evaluate expressions from left to right. We give a combinatory categorial grammar that models the syntax and the semantics of quantifier scope and wh-question formation. It allows quantificational binding but not crossover, in-situ wh but not superiority violations. In addition, the analysis automatically accounts for a variety of sentence types involving binding in the presence of pied piping, including reconstruction cases such as Whose criticism of hisi mother did each personi resent? (shrink)

Natural languages exhibit a great variety of grammatical paradigms. For instance, in English verbs are grammatically marked for tense, whereas in the tenseless Eskimo-Aleut language Kalaallisut they are marked for illocutionary mood. Although time is a universal dimension of the human experience and speaking is part of that experience, some languages encode reference to time without any grammatical tense morphology, or reference to speech acts without any illocutionary mood morphology. Nevertheless, different grammatical systems are semantically parallel in certain respects. Specifically, (...) I propose that English tenses form a temporal centering system, which monitors and updates topic times, whereas Kalaallisut moods form a modal centering system, which monitors and updates modal discourse referents. To formalize these centering parallels I define a dynamic logic that represents not only changing information but also changing focus of attention in discourse (Update with Centering, formalizing Grosz et al 1995). Different languages can be translated into this typed logic by directly compositional universal rules of Combinatory Categorial Grammar (CCG) The resulting centering theory of tense and illocutionary mood draws semantic parallels across different grammatical systems. The centering generalizations span the extremes of the typological spectrum, so they are likely to be universal. In addition, the theory accounts for the translation equivalence of tense and illocutionary mood in a given utterance context. Following Stalnaker (1978) I assume that the very act of speaking up has a ‘commonplace effect’ on the context. It focuses attention on the speech act and thereby introduces default modal and temporal topics. These universal defaults complement language-specific grammars, e.g. English tenses and Kalaallisut moods. In a given utterance context the universal discourse-initial defaults plus language-specific grammatical marking may add up to the same truth conditions.. (shrink)

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 Categorial Grammar – 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 Categorial Grammar (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 Categorial Grammar Logics [Moo98]. (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)

This article summarizes the main ideas for formalizing categorial languages genrated by classical categorial grammar 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.

A version of strong negation is introduced into Categorial Grammar. The resulting syntactic calculi turn out to be systems of connexive logic.

This paper solves a natural but still open question: can abstract categorial grammars (ACGs) respresent usual categorial grammars? Despite their name and their claim to be a unifying framework, up to now there was no faithful representation of usual categorial grammars in ACGs. This paper shows that Non-Associative Lambek grammars as well as their derivations can be defined using ACGs of order two. To conclude, the outcome of such a representation are discussed.

In [2], Bar-Hillel, Gaifman, and Shamir prove that the simple phrase structure grammars (SPGs) defined by Chomsky are equivalent in a certain sense to Bar-Hillel's bidirectional categorial grammars (BCGs). On the other hand, Cohen [3] proves the equivalence of the latter ones to what the calls free categorial grammars (FCGs). They are closely related to Lambek's syntactic calculus which, in turn, is based on the idea due to Ajdukiewicz [1]. For the reasons which will be discussed in the (...) last section, Cohen's proof seems to be at least incomplete. This paper yields a direct proof of the equivalence ofFCGs andSPGs. (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)

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 categorial grammar. 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)