Workshop on Multiple Context-Free Grammars and Related Formalisms

[Japanese | English]

National Institute of Informatics
October 5-6, 2010

The Multiple context-free grammar (MCFG) was introduced about 20 years ago by Seki, Matsumura, Fujii, and Kasami (1991). The MCFG generalizes the context-free grammar from inductive definition of sets of strings to inductive definition of sets of tuples of strings, and has been used for the description of the syntax of natural language as well as for the analysis of biological sequences. Although the formalism of MCFGs is mathematically very natural, as witnessed by the fact that it is equivalent to many other formalisms, its basic mathematical properties are not yet fully understood.

This workshop introduces the audience to the forefront of research about MCFGs, and to some of the outstanding open questions about them. It is open to all interested people.

The workshop is an activity of the NII joint research project Open Problems on Multiple Context-Free Grammars, headed by Makoto Kanazawa.

Date and Place

Date:October 5-6, 2010
Place:Rooms 2001A & B, 20th floor, National Institute of Informatics (National Center of Sciences Building). (Map and access information.)

When you enter the National Center of Sciences, tell the guard that you are attending the workshop on the 20th floor.


Makoto Kanazawa, National Institute of Informatics
Yuki Kato, Nara Institute of Science and Technology
Greg Kobele, University of Chicago
Jens Michaelis, Bielefeld University
Sylvain Salvati, INRIA Bordeaux - Sud-Ouest
Hiroyuki Seki, Nara Institute of Science and Technology
Edward Stabler, University of California, Los Angeles
Ryo Yoshinaka, Japan Science and Technology Agency


Updated October 20, 2010: PDF files of some of the presentations are available. The title provides a link to the PDF.

Tuesday, October 5

10:30Opening Session
10:40Makoto Kanazawa (NII), Multiple Context-Free Languages and Non-Duplicating Macro Languages
11:40Sylvain Salvati (INRIA Bordeaux - Sud Ouest), MIX is a 2-MCFL
14:30Open Problem Session
15:30Hiroyuki Seki (NAIST), Resource-Bounded Derivation
16:30Yuki Kato (NAIST), Computational Methods for RNA-RNA Interaction Prediction: Grammatical Approach Versus Integer Programming

Wednesay, October 6

10:40Edward Stabler (UCLA), Natural Path Sets in Multiple Context Free Grammars
11:40Jens Michaelis (Bielefeld University), Remarks on MCFGs in the Light of Minimalist Grammars
14:30Greg Kobele (University of Chicago), On Minimalist Grammars with Late Adjunction
15:30Ryo Yoshinaka (JST), Learnable Subclasses of Multiple Context-Free Grammars
16:20Closing Session

Makoto Kanazawa
kanazawa at nii

Last modified: 2010-10-22 09:08:12 JST