Citations of:
The Mathematics of Sentence Structure
Journal of Symbolic Logic 33 (4):627628 (1968)
Add citations
You must login to add citations.


The paper presents a way to transform pregroup grammars into contextfree grammars using functional composition. The same technique can also be used for the proofnets of multiplicative cyclic linear logic and for Lambek calculus allowing empty premises. 







A number of general points behind the story of this paper may be worth setting out separately, now that we have come to the end.There is perhaps one obvious omission to be addressed right away. Although the word “information” has occurred throughout this paper, it must have struck the reader that we have had nothing to say on what information is. In this respect, our theories may be like those in physics: which do not explain what “energy” is (a notion (...) 

Recently M. Szabolcs [12] has shown that many substructural logics including Lambek CalculusL are complete with respect to relativized Relational Semantics. The current paper proves that it is sufficient forL to consider a relativization to the relation x dividesy in some fixed semigroupG. 

This paper gives a simple method for providing categorial brands of featurebased unification grammars with a modeltheoretic 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 featurebased grammar logic. We demonstrate the method for the augmentation of Lambek categorial grammar with Kasper/Roundsstyle feature logic. These are combined by replacing (or annotating) atomic formulas of the first logic, i.e. the basic syntactic types, by (...) 



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 typetheoretic 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, (...) 

We show that vector space semantics and functional semantics in twosorted first order logic are equivalent for pregroup grammars. We present an algorithm that translates functional expressions to vector expressions and viceversa. The semantics is compositional, variable free and invariant under change of order or multiplicity. It includes the semantic vector models of Information Retrieval Systems and has an interior logic admitting a comprehension schema. A sentence is true in the interior logic if and only if the ‘usual’ first order (...) 

We explore a computational algebraic approach to grammar via pregroups, that is, partially ordered monoids in which each element has both a left and a right adjoint. Grammatical judgements are formed with the help of calculations on types. These are elements of the free pregroup generated by a partially ordered set of basic types, which are assigned to words, here of English. We concentrate on the object pronoun who(m). 

The problem of whether Lambek Calculus is complete with respect to (w.r.t.) relational semantics, has been raised several times, cf. van Benthem (1989a) and van Benthem (1991). In this paper, we show that the answer is in the affirmative. More precisely, we will prove that that version of the Lambek Calculus which does not use the empty sequence is strongly complete w.r.t. those relational Kripkemodels where the set of possible worlds,W, is a transitive binary relation, while that version of the (...) 



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 structurestyle 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 (...) 

In this paper we concentrate mainly on the notion of βpregroups, which are pregroups (first introduced by Lambek [18] in 1999) enriched with modality operators. βpregroups were first proposed by Fadda [11] in 2001. The motivation to introduce them was to limit (locally) the associativity in the calculus considered. In this paper we present this new calculus in the form of a rewriting system, prove the very important feature of this system  that in a given derivation the non expanding (...) 

A twostage procedure is described which induces typelogical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulaeastypes correspondence is exploited to obtain all the typelogical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt at structuredependent (...) 

Action logic of Pratt [21] can be presented as Full Lambek Calculus FL [14, 17] enriched with Kleene star *; it is equivalent to the equational theory of residuated Kleene algebras (lattices). Some results on axiom systems, complexity and models of this logic were obtained in [4, 3, 18]. Here we prove a stronger form of *elimination for the logic of *continuous action lattices and the –completeness of the equational theories of action lattices of subsets of a finite monoid and (...) 

The paper enriches the conceptual apparatus of the theory of meaning and denotation that was presented in Part I (Section 3). This part concentrates on the notion of interpretation, which is defined as an equivalence class of the relation possessing the same manner of interpreting types. In this part, some relations between meaning and interpretation, as well as one between denotation an interpretational denotation are established. In the theory of meaning and interpretation, the notion of language communication has been formally (...) 

The paper is an attempt at a logical explication of some crucial notions of current general semantics and pragmatics. A general, axiomatic, formallogical theory of meaning and interpretation is outlined in this paper.In the theory, accordingto the tokentype distinction of Peirce, language is formalised on two levels: first as a language of tokenobjects (understood as material, empirical, enduring through timeand space objects) and then – as a language of typeobjects (understood as abstract objects, as classes of tokens). The basic concepts (...) 

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 multimodal 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 (...) 

This paper develops an inference system for natural language within the ‘Natural Logic’ paradigm as advocated by van Benthem, Sánchez and others. The system that we propose is based on the Lambek calculus and works directly on the CurryHoward counterparts for syntactic representations of natural language, with no intermediate translation to logical formulae. The Lambek based system we propose extends the system by Fyodorov et~al., which is based on the Ajdukiewicz/BarHillel calculus Bar Hillel,. This enables the system to deal with (...) 





The main objective of the paper is to provide a conceptual apparatus of a general logical theory of language communication. The aim of the paper is to outline a formallogical theory of language in which the concepts of the phenomenon of language communication and language communication in general are defined and some conditions for their adequacy are formulated. The theory explicates the key notions of contemporary syntax, semantics, and pragmatics. The theory is formalized on two levels: tokenlevel and typelevel. As (...) 

The concept of linguistic infinity has had a central role to play in foundational debates within theoretical linguistics since its more formal inception in the midtwentieth century. The conceptualist tradition, marshalled in by Chomsky and others, holds that infinity is a core explanandum and a link to the formal sciences. Realism/Platonism takes this further to argue that linguistics is in fact a formal science with an abstract ontology. In this paper, I argue that a central misconstrual of formal apparatus of (...) 



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, (...) 

This work contributes to the theory of judgement aggregation by discussing a number of significant nonclassical logics. After adapting the standard framework of judgement aggregation to cope with nonclassical logics, we discuss in particular results for the case of Intuitionistic Logic, the Lambek calculus, Linear Logic and Relevant Logics. The motivation for studying judgement aggregation in nonclassical logics is that they offer a number of modelling choices to represent agents’ reasoning in aggregation problems. By studying judgement aggregation in logics that (...) 

If all dependent expressions were adjacent some variety of immediate constituent analysis would suffice for grammar, but syntactic and semantic mismatches are characteristic of natural language; indeed this is a, or the, central problem in grammar. Logical categorial grammar reduces grammar to logic: an expression is wellformed if and only if an associated sequent is a theorem of a categorial logic. The paradigmatic categorial logic is the Lambek calculus, but being a logic of concatenation the Lambek calculus can only capture (...) 

Using the programminglanguage concept of continuations, we propose a new, multimodal analysis of quantification in Type Logical Grammar. Our approach provides a geometric view of insitu quantification in terms of graphs, and motivates the limited use of empty antecedents in derivations. Just as continuations are the tool of choice for reasoning about evaluation order and side effects in programming languages, our system provides a principled, typelogical way to model evaluation order and side effects in natural language. We illustrate with an (...) 

ABSTRACTMonoidal logics were introduced as a foundational framework to analyze the proof theory of logical systems. Inspired by Lambek's seminal work in categorical logic, the objective is to defin... 

The goal of this paper is to show how modal logic may be conceived as recording the derived rules of a logical system in the system itself. This conception of modal logic was propounded by Dana Scott in the early seventies. Here, similar ideas are pursued in a context less classical than Scott's.First a family of propositional logical systems is considered, which is obtained by gradually adding structural rules to a variant of the nonassociative Lambek calculus. In this family one (...) 

Substructural logics are logics obtained from a sequent formulation of intuitionistic or classical logic by rejecting some structural rules. The substructural logics considered here are linear logic, relevant logic and BCK logic. It is proved that firstorder variants of these logics with an intuitionistic negation can be embedded by modal translations into S4type extensions of these logics with a classical, involutive, negation. Related embeddings via translations like the doublenegation translation are also considered. Embeddings into analogues of S4 are obtained with (...) 

The paper concentrates on the problem of adequate reflection of fragments of reality via expressions of language and intersubjective knowledge about these fragments, called here, in brief, language adequacy. This problem is formulated in several aspects, the most being: the compatibility of language syntax with its bilevel semantics: intensional and extensional. In this paper, various aspects of language adequacy find their logical explication on the ground of the formallogical theory T of any categorial language L generated by the socalled classical (...) 

Every language recognized by the Lambek calculus with brackets is contextfree. This is shown by combining an observation by Jäger with an entirely straightforward adaptation of the method Pentus used for the original Lambek calculus. The case of the variant of the calculus allowing sequents with empty antecedents is slightly more complicated, requiring a restricted use of the multiplicative unit. 

We look at lower semilatticeordered residuated semigroups and, in particular, the representable ones, i.e., those that are isomorphic to algebras of binary relations. We will evaluate expressions in representable algebras and give finite axiomatizations for several notions of validity. These results will be applied in the context of substructural logics. 



The Distributional Compositional Categorical model is a mathematical framework that provides compositional semantics for meanings of natural language sentences. It consists of a computational procedure for constructing meanings of sentences, given their grammatical structure in terms of compositional typelogic, and given the empirically derived meanings of their words. For the particular case that the meaning of words is modelled within a distributional vector space model, its experimental predictions, derived from real large scale data, have outperformed other empirically validated methods that (...) 

Pentus (1992) proves the equivalence of LCG's and CFG's, and CFG's are equivalent to BCG's by the Gaifman theorem (BarHillel et al., 1960). This paper provides a procedure to extend any LCG to an equivalent BCG by affixing new types to the lexicon; a procedure of that kind was proposed as early, as Cohen (1967), but it was deficient (Buszkowski, 1985). We use a modification of Pentus' proof and a new proof of the Gaifman theorem on the basis of the (...) 

Many variants of categorial grammar assume an underlying logic which is associative and linear. In relation to left extraction, the former property is challenged by island domains, which involve nonassociativity, and the latter property is challenged by parasitic gaps, which involve nonlinearity. We present a version of type logical grammar including ‘structural inhibition’ for nonassociativity and ‘structural facilitation’ for nonlinearity and we give an account of relativisation including islands and parasitic gaps and their interaction. 

Lecture notes from Husserl's logic lectures published during the last 20 years offer a much better insight into his doctrine of the forms of meaning than does the fourth Logical Investigation or any other work published during Husserl's lifetime. This paper provides a detailed reconstruction, based on all the sources now available, of Husserl's system of logical grammar. After having explained the notion of meaning that Husserl assumes in his later logic lectures as well as the notion of form of (...) 

Monoidal logics were introduced as a foundational framework to analyse the proof theory of deontic logic. Building on Lambek’s work in categorical logic, logical systems are defined as deductive systems, that is, as collections of equivalence classes of proofs satisfying specific rules and axiom schemata. This approach enables the classification of deductive systems with respect to their categorical structure. When looking at their proof theory, however, one can see that there are similarities between monoidal and substructural logics. The purpose of (...) 

This article presents modal versions of resourceconscious logics. We concentrate on extensions of variants of linear logic with one minimal nonnormal modality. In earlier work, where we investigated agency in multiagent systems, we have shown that the results scale up to logics with multiple nonminimal modalities. Here, we start with the language of propositional intuitionistic linear logic without the additive disjunction, to which we add a modality. We provide an interpretation of this language on a class of Kripke resource models (...) 

We consider language models for the Lambek calculus that allow empty antecedents and enrich them with constants for the empty language and for the language containing only the empty word. No complete calculi are known with respect to these semantics, and in this paper we consider several trivalent systems that arise as fragments of these models? logics. 

The Polish logicians' propositional calculi, which consist in a distinct synthesis of the Fregean and Boolean approaches to logic, influenced W. V. Quine's early work in formal logic. This early formal work of Quine's, in turn, can be shown to serve as one of the sources of his holistic conception of natural language. 

This paper is concerned with De Morgan?s explanation of the validity of arguments that involve relational notions. It discusses De Morgan?s expansion of traditional logic aimed at accommodating those inferences, and makes the point that his endeavour is not successful in that the rules that made up his new logic are not sound. Nevertheless, the most important scholarly work on De Morgan?s logic, and contrary to that De Morgan?s mistake is not beyond repair. The rules that determine his new logic (...) 

In this paper we compare grammatical inference in the context of simple and of mixed Lambek systems. Simple Lambek systems are obtained by taking the logic of residuation for a family of multiplicative connectives /,,\, together with a package of structural postulates characterizing the resource management properties of the connective.Different choices for Associativity and Commutativity yield the familiar logics NL, L, NLP, LP. Semantically, a simple Lambek system is a unimodal logic: the connectives get a Kripke style interpretation in terms (...) 

The LambekGrishin calculus is a symmetric version of categorial grammar obtained by augmenting the standard inventory of typeforming 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 CurryHoward derivational semantics, and structurepreservation at the syntactic end. The move to symmetry thus offers novel ways of reconciling the demands of natural language (...) 

