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)

We introduce non-associative linear logic, which may be seen as the classical version of the non-associative Lambek calculus. We define its sequent calculus, its theory of proof-nets, for which we give a correctness criterion and a sequentialization theorem, and we show proof search in it is polynomial.

We review the properties of Global Index Grammars (GIGs), a grammar formalism that uses a stack of indices associated with productions and has restricted context-sensitive power. We show how the control of the derivation is performed and how this impacts in the descriptive power of this formalism both in the string languages and the structural descriptions that GIGs can generate.

Symmetric generalized Galois logics (i.e., symmetric gGl s) are distributive gGl s that include weak distributivity laws between some operations such as fusion and fission. Motivations for considering distribution between such operations include the provability of cut for binary consequence relations, abstract algebraic considerations and modeling linguistic phenomena in categorial grammars. We represent symmetric gGl s by models on topological relational structures. On the other hand, topological relational structures are realized by structures of symmetric gGl s. We generalize the weak (...) distributivity laws between fusion and fission to interactions of certain monotone operations within distributive super gGl s. We are able to prove appropriate generalizations of the previously obtained theorems—including a functorial duality result connecting classes of gGl s and classes of structures for them. (shrink)

Using the programming-language concept of continuations, we propose a new, multimodal analysis of quantification in Type Logical Grammar. Our approach provides a geometric view of in-situ 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, type-logical way to model evaluation order and side effects in natural language. We illustrate with an (...) improved account of quantificational binding, weak crossover, wh-questions, superiority, and polarity licensing. (shrink)

This paper proposes that the meanings of some natural language expressions should be thought of as functions on their own continuations. Continuations are a well-established analytic tool in the theory of programming language semantics; in brief, a continuation is the entire default future of a computation. I show how a continuation-based grammar can unify several aspects of natural language quantification in a new way: merely stating the truth conditions for quantificational expressions in terms of continuations automatically accounts for scope displacement (...) and scope ambiguity. To prove this claim, I exhibit a simple finite context-free grammar with a strictly compositional semantics in which quantificational NPs are interpreted in situ but take semantic scope over larger constituents. There is no Quantifier Raising (nor any use of a level of Logical Form distinct from overt syntax), no Cooper Storage (or similar mechanisms used in many recent HPSG, Categorial, or Type-logical treatments), and no need for type-shifting (as in Hendriks' Flexible Types account). Continuations also provide a natural account of generalized coordination that does not require either type-shifting or type polymorphism. Compositionality issues are discussed in some detail. (shrink)

Recent developments in the semantics of natural language seem to lead to a genuine synthesis of ideas from linguistics and logic, producing novel concepts and questions of interest to both parent disciplines. This book is a collection of essays on such new topics, which have arisen over the past few years. Taking a broad view, developments in formal semantics over the past decade can be seen as follows. At the beginning stands Montague's pioneering work, showing how a rigorous semantics can (...) be given for complete fragments of natural language by creating a suitable fit between syntactic categories and semantic types. This very enterprise already dispelled entrenched prejudices concerning the separation of linguistics and logic. Having seen the light, however, there is no reason at all to stick to the letter of Montague's proposals, which are often debatable. Subsequently, then, many improvements have been made upon virtually every aspect of the enterprise. More sophisticated grammars have been inserted (lately, lexical-functional grammar and generalized phrase structure grammar), more sensitive model structures have been developed (lately, 'partial' rather than 'total' in their com position), and even the mechanism of interpretation itself may be fine-tuned more delicately, using various forms of 'representations' mediating between linguistic items and semantic reality. In addition to all these refinements of the semantic format, descriptive coverage has extended considerably. (shrink)

In 1958 J. Lambek introduced a calculusL of syntactic types and defined an equivalence relation on types: x y means that there exists a sequence x=x1,...,xn=y (n 1), such thatx i x i+1 or xi+ x i (1 i n). He pointed out thatx y if and only if there is joinz such thatx z andy z. This paper gives an effective characterization of this equivalence for the Lambeck calculiL andLP, and for the multiplicative fragments of Girard's and Yetter's linear (...) logics. Moreover, for the non-directed Lambek calculusLP and the multiplicative fragment of Girard's linear logic, we present linear time algorithms deciding whether two types are equal, and finding a join for them if they are. (shrink)

We present a novel way of using proof nets for the multimodal Lambek calculus, which provides a general treatment of both the unary and binary connectives. We also introduce a correctness criterion which is valid for a large class of structural rules and prove basic soundness, completeness and cut elimination results. Finally, we will present a correctness criterion for the original Lambek calculus Las an instance of our general correctness criterion.

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 (...) of a single ternary accessibility relation modeling the notion of linguistic composition for each individual system.The simple systems earch have their virtues in linguistic analysis. But none of them in isolation provides a basis for a full theory of grammar. In the second part of the paper, we consider two types of mixed Lambek systems. (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)

Substructural logics are traditionally obtained by dropping some or all of the structural rules from Gentzen's sequent calculi LK or LJ. It is well known that the usual logical connectives then split into more than one connective. Alternatively, one can start with the Lambek calculus, which contains these multiple connectives, and obtain numerous logics like: exponential-free linear logic, relevant logic, BCK logic, and intuitionistic logic, in an incremental way. Each of these logics also has a classical counterpart, and some also (...) have a 'cyclic' counterpart. These logics have been studied extensively and are quite well understood.Generalising further, one can start with intuitionistic Bi-Lambek logic, which contains the dual of every connective from the Lambek calculus. The addition of the structural rules then gives Bi-linear, Bi-relevant, Bi-BCK and Bi-intuitionistic logic, again in an incremental way. Each of these logics also has a classical counterpart, and some even have a 'cyclic' counterpart. These extensions of Bi-Lambek logic are not so well understood. Cut-elimination for Classical Bi-Lambek logic, for example, is not completely clear since some cut rules have side conditions requiring that certain constituents be empty or non-empty.The display logic of Nuel Belnap is a general Gentzen-style proof theoretical framework designed to capture many different logics in one uniform setting. The beauty of display logic is a general cut-elimination theorem, due to Belnap, which applies whenever the rules of the display calculus obey certain, easily checked, conditions. The original display logic, and its various incarnations, are not suitable for capturing bi-intuitionistic and bi-classical logics in a uniform way. We remedy this situation by giving a single Display calculus for the Bi-Lambek Calculus, from which all the well-known extensions are obtained by the incremental addition of structural rules to a constant core of logical introduction rules.We highlight the inherent duality and symmetry within this framework obtaining 'four proofs for the price of one'. We give algebraic semantics for the Bi-Lambek logics and prove that our calculi are sound and complete with respect to these semantics. We show how to define an alternative display calculus for bi-classical substructural logics using negations, instead of implications, as primitives.Borrowing from other display calculi, we show how to extend our display calculus to handle bi-intuitionistic or bi-classical substructural logics containing the forward and backward modalities familiar from tense logic, the exponentials of linear logic, the converse operator familiar from relation algebra, four negations, and two unusual modalities corresponding to the non-classical analogues of Sheffer's 'dagger' and 'stroke', all in a modular way.Using the Gaggle Theory of Dunn we outline relational semantics for the binary and unary intensional connectives, but make no attempt to do so for the extensional connectives, or the exponentials.Finally, we flesh out a suggestion of Lambek to embed intuitionistic logic using two unusual 'exponentials', and show that these 'exponentials' are essentially tense logical modalities, quite at odds with the usual exponentials.Using a refinement of the display property, you can pick and choose from these possibilities to construct a display calculus for your needs. (shrink)

Algebraic work [9] shows that the deep theory of possible world semantics is available in the more general setting of substructural logics, at least in an algebraic guise. The question is whether it is also available in a relational form.This article seeks to set the stage for answering this question. Guided by the algebraic theory, but purely relationally we introduce a new type of frames. These structures generalize Kripke structures but are two-sorted, containing both worlds and co-worlds. These latter points (...) may be viewed as modelling irreducible increases in information where worlds model irreducible decreases in information. Based on these structures, a purely model theoretic and uniform account of completeness for the implication-fusion fragment of various substructural logics is given. Completeness is obtained via a generalization of the standard canonical model construction in combination with correspondence results. (shrink)

This comprehensive text shows how various notions of logic can be viewed as notions of universal algebra providing more advanced concepts for those who have an introductory knowledge of algebraic logic, as well as those wishing to delve into more theoretical aspects.

Language in Action demonstrates the viability of mathematical research into the foundations of categorial grammar, a topic at the border between logic and linguistics. Since its initial publication it has become the classic work in the foundations of categorial grammar. A new introduction to this paperback edition updates the open research problems and records relevant results through pointers to the literature. Van Benthem presents the categorial processing of syntax and semantics as a central component in a more general dynamic logic (...) of information flow, in tune with computational developments in artificial intelligence and cognitive science. Using the paradigm of categorial grammar, he describes the substructural logics driving the dynamics of natural language syntax and semantics. This is a general type-theoretic approach that lends itself easily to proof-theoretic and semantic studies in tandem with standard logic. The emphasis is on a broad landscape of substructural categorial logics and their proof-theoretical and semantic peculiarities. This provides a systematic theory for natural language understanding, admitting of significant mathematical results. Moreover, the theory makes possible dynamic interpretations that view natural languages as programming formalisms for various cognitive activities. (shrink)

Nonclassical logics have played an increasing role in recent years in disciplines ranging from mathematics and computer science to linguistics and philosophy. _Generalized Galois Logics_ develops a uniform framework of relational semantics to mediate between logical calculi and their semantics through algebra. This volume addresses normal modal logics such as K and S5, and substructural logics, including relevance logics, linear logic, and Lambek calculi. The authors also treat less-familiar and new logical systems with equal deftness.

This book takes concepts developed by researchers in theoretical computer science and adapts and applies them to the study of natural language meaning. Summarizing over a decade of research, Chris Barker and Chung-chieh Shan put forward the Continuation Hypothesis: that the meaning of a natural language expression can depend on its own continuation.

This comprehensive text shows how various notions of logic can be viewed as notions of universal algebra providing more advanced concepts for those who have an introductory knowledge of algebraic logic, as well as those wishing to delve into more theoretical aspects.