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)

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order operation in the case of linear context-free rewriting (...) systems. This suggest the possibility of defining an Abstract Categorial Hierarchy. (shrink)

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.

This paper solves a natural but still open question: can abstract categorial grammars 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 this paper we show that the membership problem for second order non-linear Abstract Categorial Grammars is decidable. A consequence of that result is that Montague-like semantics yield to a decidable text generation problem. Furthermore the proof we propose is based on a new tool, Higher Order Intersection Signatures, which grasps statically dynamic properties of λ-terms and presents an interest in its own.

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order operation in the case of linear context-free rewriting (...) systems. This suggest the possibility of defining an Abstract Categorial Hierarchy. (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)

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)

This paper argues for the idea that in describing language we should follow Haskell Curry in distinguishing between the structure of an expression and its appearance or manifestation . It is explained how making this distinction obviates the need for directed types in type-theoretic grammars and a simple grammatical formalism is sketched in which representations at all levels are lambda terms. The lambda term representing the abstract structure of an expression is homomorphically translated to a lambda term representing its (...) manifestation, but also to a lambda term representing its semantics. (shrink)

Words have meaning. Sentences also have meaning, but their meaning is different in kind from any collection of the meanings of the words they contain. I discuss two puzzles related to this difference. The first is how the meanings of the parts of a sentence combine to give rise to a unified sentential meaning, as opposed to a mere collection of disparate meanings (UP1). The second is why the formal ontology of linguistic meaning changes when grammatical structure is built up (...) (UP2). For example, the meaning of a sentence is a proposition evaluable for truth and falsity. In contrast, a collection of the meanings of its parts does not constitute a proposition and is not evaluable for truth. These two puzzles are closely related, since change in formal ontology is the clearest sign of the unity of meaning. The most popular strategy for answering them is taking the meanings of the parts as abstractions from primitive sentence meanings. However, I argue that, given plausible psychological constraints, sentence meanings cannot be taken as explanatory primitives. Drawing on recent work in Generative Grammar and its philosophy, I suggest that the key to both unity questions is to distinguish strictly between lexical and grammatical meaning. The latter is irreducible and determines how lexical content is used in referential acts. I argue that these referential properties determine a formal ontology, which explains why and how formal ontology changes when grammatical structure is built up (UP2). As for UP1, I suggest that, strictly speaking, lexical meanings never combine. Instead, whenever grammar specifies a formal ontology for the lexical meanings entering a grammatical derivation, further lexical (or phrasal) meanings can only specify aspects of this recursive grammatical process. In this way, contemporary grammatical theory can be used to address old philosophical problems. (shrink)

Embodied cognitive theories predict that linguistic conceptual representations are grounded and continually represented in real world, sensorimotor experiences. However, there is an on-going debate on whether this also holds for abstract concepts. Grammar is the archetype of abstract knowledge, and therefore constitutes a test case against embodied theories of language representation. Former studies have largely focussed on lexical-level embodied representations. In the present study we take the grounding-by-modality idea a step further by using reaction time (RT) data (...) from the linguistic processing of nominal classifiers in Chinese. We take advantage of an independent body of research, which shows that attention in hand space is biased. Specifically, objects near the hand consistently yield shorter RTs as a function of readiness for action on graspable objects within reaching space, and the same biased attention inhibits attentional disengagement. We predicted that this attention bias would equally apply to the graspable object classifier but not to the big object classifier. Chinese speakers (N = 22) judged grammatical congruency of classifier-noun combinations in two conditions: graspable object classifier and big object classifier. We found that RTs for the graspable object classifier were significantly faster in congruent combinations, and significantly slower in incongruent combinations, than the big object classifier. There was no main effect on grammatical violations, but rather an interaction effect of classifier type. Thus, we demonstrate here grammatical category- specific effects pertaining to the semantic content and by extension the visual and tactile modality of acquisition underlying the acquisition of these categories. We conclude that abstract grammatical categories are subjected to the same mechanisms as general cognitive and neurophysiological processes and may therefore be grounded. (shrink)

The paper contains an overview of the most important results presented in the monograph of the author "Teorie Językow Syntaktycznie-Kategorialnych" ("Theories of Syntactically-Categorial Languages" (in Polish), PWN, Warszawa-Wrocław 1985. In the monograph four axiomatic systems of syntactically-categorial languages are presented. The first two refer to languages of expression-tokens. The others also takes into consideration languages of expression-types. Generally, syntactically-categorial languages are languages built in accordance with principles of the theory of syntactic categories introduced by S. Leśniewski [1929,1930]; (...) they are connected with- the Ajdukiewicz’s work [1935] which was a continuation of Leśniewski’s idea and further developed and popularized in the research on categorial grammars, by Y. Bar-Hillel [1950,1953,1964]. To assign a suitable syntactic category to each word of the vocabulary is the main idea of syntactically-categorial approach to language. Compound expressions are built from the words of the vocabulary and then a suitable syntactic-category is assigned to each of them. A language built in this way should be decidable, which means that there should exist an algorithm for deciding about each expression of it, whether it is well-formed or is syntactically connected . The traditional, originating from Husserl, understanding of the syntactic category confronts some difficulties. This notion is defined by abstraction using the concept of affiliation of two expressions to the same syntactic category. (shrink)

This paper examines early syntactic development from a usage-based perspective, using transcripts of the spontaneous speech of two Englishspeaking children recorded at relatively dense intervals at ages 2;0 and 3;0. We focus primarily on the children’s question constructions, in an effort to determine (i) what kinds of units they initially extract from the input (their size and degree of specificity / abstractness); (ii) what operations they must perform in order to construct novel utterances using these units; and (iii) how the (...) units and the operations change between the ages of two and three. In contrast to nativist theories of language development which suggest that children are working with abstract syntactic categories from an early point in development, we suggest that the data are better accounted for by the proposal that children begin with lexically specific phrases and gradually build up a repertoire of increasingly abstract constructions. (shrink)

Since its formal definition over sixty years ago, category theory has been increasingly recognized as having a foundational role in mathematics. It provides the conceptual lens to isolate and characterize the structures with importance and universality in mathematics. The notion of an adjunction (a pair of adjoint functors) has moved to center-stage as the principal lens. The central feature of an adjunction is what might be called "internalization through a universal" based on universal mapping properties. A recently developed "heteromorphic" theory (...) of adjoint functors allows the concepts to be more easily applied empirically. This suggests a conceptual structure, albeit abstract, to model a range of selectionist mechanisms (e.g., in evolution and in the immune system). Closely related to adjoints is the notion of a "brain functor" which abstractly models structures of cognition and action (e.g., the generative grammar view of language). (shrink)

This paper argues that grammatical constructions, specifically argument structure constructions that determine the “who did what to whom” part of sentence meaning and how this meaning is expressed syntactically, can be considered a kind of relational category. That is, grammatical constructions are represented as the abstraction of the syntactic and semantic relations of the exemplar utterances that are expressed in that construction, and it enables the generation of novel exemplars. To support this argument, I review evidence that there are parallel (...) behavioral patterns between how children learn relational categories generally and how they learn grammatical constructions specifically. Then, I discuss computational simulations of how grammatical constructions are abstracted from exemplar sentences using a domain-general relational cognitive architecture. Last, I review evidence from adult language processing that shows parallel behavioral patterns with expert behavior from other cognitive domains. After reviewing the evidence, I consider how to integrate this account with other theories of language development. (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)

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.

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.

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)

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)

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)

This commentary discusses the division of labor between syntax and phonology, starting with the parallel model of grammar developed by Jackendoff. It is proposed that linear, left-to-right order of linguistic items is not represented in syntax, but in phonology. Syntax concerns the abstract relations of categories alone. All components of grammar contribute to linear order, by means of the interface rules.

There is a widespread assumption in Construction Grammar that the meanings of verbs correlate with or even determine their complementation forms and patterns. There is much less research on noun complementation, however, although this category is even more interesting for a number of reasons such as the potential for valency reduction, nominal topicalization constructions, and additional complementation options, e.g.of-PPs and existential constructions.In this paper we focus on the class of nouns reporting commissive illocutionary acts, and address the question of (...) whether there is a correlation between the meaning of these nouns and their preferred complementation patterns, and between their semantic similarity and their similarity in the distribution of complementation patterns.We report the results of a study of a set of 17 commissive nouns chosen from a wider collection of illocutionary nouns. Two types of analysis were carried out in order to compare the semantic and grammatical characteristics of these nouns. The semantic analysis was based on insights from speech act theory and the philosophy of language. We developed a framework for a systematic comparative description of the nouns in our word field. The results were tallied with a corpus-based grammatical analysis. Two hundred tokens of each noun type were randomly sampled from the Corpus of Contemporary American English. Using these data, the 17 nouns were subjected to an analysis of the relative frequencies of their complementation patterns.Results indicate a general match between noun meanings and complementation patterns. More specifically, however, they indicate that the closeness of this match depends on the prototypicality of nouns as members of the class of commissives.The study, then, contributes to our understanding of the relation between lexis and syntax. At the same time, it confirms the need for a close semantic analysis to account for the great extent to which item-specific information, i.e. properties of individual nouns, have to be taken into consideration at the expense of large-scale generalizations. (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)

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.

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)

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

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)

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)

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)

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)

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)