# 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

- Carlos Areces
- Chris Barker
- Paul Bédaride
- Gilad Ben-Avi
- Luciana Benotti
- Patrick Blackburn
- Anna Chernilovskya
- Marie-Renée Fleury
- Philippe de Groote
- Bruno Guillaume
- Sébastien Hinderer
- Guillaume Hoffmann
- Makoto Kanazawa
- François Lamarche
- Alain Lecomte
- Sarah Maarek
- Glyn Morrill
- Michael Moortgat
- Reinhard Muskens
- Sylvain Pogodalla
- Carl Pollard
- Myriam Quatrini
- Sylvain Salvati
- Lutz Strassburger
- Christina Unger
- Yoad Winter
- Ryo Yoshinaka

# 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

#### 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.).

#### Philippe de Groote: Yet another dynamic logic

#### 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.

#### 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.

#### Chris Barker: Reasonning about contexts in Lambek Grammars

#### 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.

#### 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.

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

#### 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.

#### 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.

#### 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.

# 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

- Sylvain Pogodalla:

*Last modification: 2007-10-02
*