Third Workshop on Lambda Calculus and Formal Grammar: abstracts

Because of their apparent type mismatch between syntax and semantics, scope ambiguity phenomena have motivated a lot of work in modeling the syntax/semantic interface. I will show how we can accomodate some of them, and propose a new one, in the ACG framework.

Although intensionality has been substantially studied in the literature, the divison of labor between different parts of the theory were not extensively discussed. We propose a modular approch to intensional systems, which involves three stages in their construction:

1. Developping a purely extensional semantics.
2. "Intensionalizing" this semantics: adding the necessary logical types and domains for obtaining intensionality, while at the same time preserving provable extensionality in a strict sense.
3. Adding intension-sensitive entries to the lexicon.

We contend that this architecture allows a simple dissociation between extensional mechanisms like scope, quantification and coordination, and intensionality phenomena stemming from particular lexical entries.

We show some advantages of the abstract CG/lambda-grammar methodology in allowing a simple use of extensional scope mechanisms for treating "de re" interpretations in intensional contexts.

Joint work with Gilad Ben-Avi

In this talk I will define what I call 'intensional' models for the classical theory of types, thus arriving at a hyperintensional (i.e. truly intensional, not just modal) type logic ITL. Intensional models generalize Henkin's general models and have a natural and rather simple definition. The classical Gentzen rules for the logical operators remain valid under the generalization, and in fact a simple cut-free sequent calculus consisting of such classical rules characterizes the new semantic entailment relation completely. This means that with intensional models, whose main characteristic is that they distinguish between the sense (intension) and the reference (extension) of any given relation, we are still within the confines of classical logic. But, crucially, the axiom of Extensionality is no longer valid: two relations can have the same extension without having the same properties.

There are two applications of the logic I will discuss. Firstly, I will argue that, since ITL is truly intensional, it can be used to model ascriptions of propositional attitude without predicting logical omniscience. In order to illustrate this a small fragment of English will be defined and be provided with an ITL semantics. Secondly, it will be shown that ITL models contain certain objects that can be identified with possible worlds. Essential elements of modal logic become available within classical type theory once the axiom of Extensionality is given up.

The complexity class LOGCFL is the class of sets LOGSPACE reducible to context-free languages. Surprizingly, this class has alternative characterizations based on Boolean ciucuits, algebraic structures, and logic. In this talk, we will survey these results and discuss open problems.

I show that the problems of parsing and generation for grammar formalisms with "context-free" derivations, coupled with Montague semantics (with a certain restriction) can be reduced in a uniform way to Datalog, function-free Horn-clause logic programming. This reduction has three consequences: (i) the search problem of computing all derivation trees (in the form of a shared forest) from an input string/logical form is in functional PTIME; (ii) the decision problem of recognizing grammaticality/surface realizability of an input string/logical form is in LOGCFL; (iii) the search problem of finding one logical form/surface string from an input string/logical form is in functional LOGCFL.