Lambda Calculus and Formal Grammar

Lambda Calculus and Formal Grammar

4th workshop

Sep. 18-19 2007, Nancy (France)

With gratefully acknowledge support of

The INRIA Associate Team program

Lambda & Grammars

The NWO Internationalisation in the Humanities program

A Global Network for Lambda Grammars and Abstract Categorial Grammars

Presentation

The LCFG workshop series aims at promoting research results on formal grammars and natural language models from a type-theoretic point of view. It gives a special emphasis to the grammatical formalism of Abstract Categorial Grammar, Lambda Grammar and related formalisms.

Participants

Program

Tuesday September 18th

10:00 Welcome and opening
10:20 Reinhard Muskens English as a formal system (slides)
11:00 Break
11:30 Gilad Ben-Avi/Yoad Winter A sound intensionalization procedure
12:10 Philippe de Groote Yet another dynamic logic (slides)
12:50 Lunch
14:30 Sébastien Hinderer Compositional approaches to discourse representation structures construction (slides)
15:10 Christina Unger Feature-driven movement as delimited control (slides)
15:50 Break
16:20 Chris Barker Reasonning about contexts in Lambek Grammars (slides)

Wednesday September 19th

09:40 Makoto Kanazawa Almost Linear Abstract Categorial Grammars and Attribute Grammars (slides)
10:20 Michael Moortgat Lexical and derivational semantics for Lambek-Grishin calculus
11:00 Break
11:30 Carl Pollard The Logics of Overt and Covert Movement in aRelational Type-Theoretic Grammar (slides)
12:10 Glyn Morrill Grammar and Incremental processing of Dutch word order (slides)
12:50 Lunch
14:45 Sylvain Salvati On grammatical analyses of Lambek grammars (slides)
15:25 Ryo Yoshinaka On two extensions of Abstract Categorial Grammars (slides)
16:05 Closing

Abstracts

Reinhard Muskens: English as a Formal System

Slides

Back to the program.

Gilad Ben-Avi: A sound intensionalization procedure

(Joint work with Yoad Winter)

In this talk we present a procedure that takes a simple version of extensional semantics and generates from it an equivalent possible-world semantics that is suitable for treating intensional phenomena in natural language. This process of intensionalization is proved to be sound in the sense that it preserves entailments between derivations of sentences.

The intensionalization process allows to treat intensional phenomena as stemming exclusively from the lexical meaning of words like believe, need or fake. We illustrate the proposed intensionalization technique using an extensional toy fragment. This fragment is used to show that independently motivated extensional mechanisms for scope shifting and verb-object composition, once properly intensionalized, are strictly speaking responsible for certain intensional effects, including de dicto/de re ambiguities and coordinations containing intensional transitive verbs. While such extensional-intensional relations have often been assumed in the literature, this talk offers a formal sense for this claim, facilitating the dissociation between extensional semantics and intensional semantics.

The sound intensionalization procedure presented in this talk improves an earlier version of this work, based on a proposal by Makoto Kanazawa, Philippe de Groote and Reinhard Muskens (p.c.).

Back to the program.

Philippe de Groote: Yet another dynamic logic

Slides

Back to the program.

Sébastien Hinderer: Compositional approaches to discourse representation structures construction

In his paper ``Combining Montague Semantics and Discourse Representation'' (1995), Reinhard Muskens shows how DRSs can be represented by certain TY_3 lambda-terms, and how it is possible to make the computation of such DRSs completely compositional, from the lexical to the inter-sentential level. 11 years later, Philippe de Groote, in his paper ``Towards a Montagovian Account of Dynamics'', proposes analternative, TY_2-based encoding of DRSs. In this talk, we present both approaches and show how they have been successfully implemented using the Nessie tool we designed for automating semantic construction in TY_n. We then compare the two approaches from a computational point of view. Rather than a presentation of mature results, this comparison aims at being a kind invitation for discussions and exchanges.

Slides

Back to the program.

Christina Unger: Feature-driven movement as delimited control

Minimalist Grammars (MG) and type-logical deductive frameworks are closely related, as was indicated and explored by many researchers. This connection has been illuminated mainly by developing Minimalist ideas in Multimodal Categorial Grammars (MMCG). I want to reverse this perspective and explore how the use of control operators for a semantics of feature-driven movement in MG would correspond to MMCG implementations of Minimalism.

Slides

Back to the program.

Chris Barker: Reasonning about contexts in Lambek Grammars

Handout Slides

Back to the program.

Makoto Kanazawa: Almost Linear Abstract Categorial Grammars and Attribute Grammars

An "almost linear" lambda term is like a linear lambda term except that a variable may occur free more than once in the same subterm when it has an atomic type. Almost linear second-order ACGs retain many of the formal properties of linear second-order ACGs and generalize some well-known non-linear grammar formalisms like IO context-free tree grammars. In this talk, I show that "simple multi-visit" attribute grammars can be represented by almost linear second-order ACGs. As a consequence, almost linear second-order ACGs and attribute grammars whose semantic domain is the free algebra of trees generate exactly the same class of tree languages.

Slides

Back to the program.

Michael Moortgat: Lexical and derivational semantics for Lambek-Grishin calculus

(Joint work with Raffaella Bernardi)

Derivations in the symmetric Lambek-Grishin calculus LG are mapped to lambda terms (coding meaning composition) by means of a continuation-passing-style (CPS) transformation. The domains of interpretation at the CPS level are more structured than those of a direct Montague-style interpretation. To obtain an interface with the CPS target language, we study type transitions lifting the lexical constants of the direct interpretation to the corresponding CPS level. The terms associated with these transitions, in addition to the lexical constants of the source language, can make use of combinators (pure lambda terms).

By providing continuation semantics for unary (residuated, Galois connected) modalities, we obtain a choice between localizing the action of these combinators at the lexical or at the derivational level. We illustrate with scope islands.

Back to the program.

Carl Pollard: The Logics of Overt and Covert Movement in a Relational Type-Theoretic Grammar

Slides

Back to the program.

Glyn Morrill: Grammar and incremental processing of Dutch word order

(Joint work with Oriol Valentín and Mario Fadda)

Dutch subordinate clauses exhibit cross-serial dependencies, but an increasing load in processing makes such multiple embeddings increasingly unacceptable. In this paper we formulate Type Logical Grammar for basic Dutch word order using Discontinuous Lambek Calculus, in particular 1-DL, the Discontinuous Lambek Calculus with one point of discontinuity. Although proof nets for this calculus are not fully developed, we are able to see their form, and how the unacceptability of multiple embeddings can be hypothesized as arising from load on short term working memory of incremental processing.

Slides

Back to the program.

Sylvain Salvati: On grammatical analyses of Lambek grammars

(Joint work with Makoto Kanazawa)

In this talk we investigate, from a formal language perspective, the properties of the set of proofs that account for the grammaticality of the correct sentences of a Lambek grammar. It has been claimed (Tiede 98) that this set of proofs, seen as a set of natural deduction trees in normal form, could be defined as the language of some context free tree grammar, we show that this claim is false. We then show how the proof that Pentus gave of the context-freeness of the languages defined by Lambek grammars can be used to give a straightforward embedding of Lambek grammars within second order Abstract Categorial Grammars (ACGs). The tight link between second order ACGs and hyperedge replacement grammars (Kanazawa 2007) suggests a definition of the set of cut-free proof-nets representing grammatical analyses of a Lambek grammar as the language of a hyperedge replacement grammars. This study gives a rather precise account of the language theoretic complexity of the proofs representing the grammatical derivations of Lambek grammars. Furthermore, this perspective sheds some light on the so-called problem of the strong equivalence between context free grammars and Lambek grammars. Indeed, it shows that any compositional semantics for a Lambek grammar can be represented as a compositional semantics on a context free grammar. Thus, even though the proof-structures of Lambek grammars may seem more subtle than the derivation trees of context free grammars, they don't allow to define richer relations between syntax and semantics than context free grammars ; we may argue that they may, on the other hand, define this relation in a more subtle way.

Slides

Back to the program.

Ryo Yoshinaka: On two extensions of Abstract Categorial Grammars

(Joint work with Philippe de Groote and Sarah Maarek)

The ACGs are a type theoretic grammar formalism intended for the description of natural languages. While the original definition is based on the implicative fragment of linear logic, recently De Groote and Maarek have proposed some type theoretic extensions of ACGs. This talk shows that two extensions of them, ACGs with Cartesian product and ACGs with dependent product, result in Turing-complete formalisms in which any recursively enumerable languages are generated.

Slides

Back to the program.

Practical

The workshop will take place at the LORIA, in room B013. General instructions to come at the LORIA can be found here and a map of the campus, with the main bus and tram stops is here.

Informations on local public transportation are here.

Former Workshops

Contact

Last modification: 2007-10-02