Second Workshop on Multiple Context-Free Grammars and Related Formalisms

Nara International Seminar House, September 9–10

This was a sequel to the First Workshop on Multiple Context-Free Grammars, and was held as a satellite workshop to the 12th Meeting on Mathematics of Language.

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, many of its basic mathematical properties have only recently come to be fully understood.

This workshop introduced the audience to the forefront of research about MCFGs, including solutions to some long-lasting open questions. It was 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:September 9–10, 2011
Place:Nara International Seminar House


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


Pierre Bourreau
Alex Clark
Kit Fine
Timothy Fowler
Kenji Hashimoto
Mauricio Hernandes
Tim Hunter
Naoki Kobayashi
Andreas Maletti
Matthew Skala
Taro Suzuki
Christian Wurm


The program of the workshop consisted of eight one-hour tutorials. The titles below provide links to the PDF files used for the presentation.

Hiroyuki Seki. Multiple Context-Free Grammars: Basic Properties and Complexity.
Greg Kobele. The linguistic relevance of MCFLs.
Jens Michaelis. Equivalence to Minimalist Grammars: All boils down to overt phrasal movement.
Makoto Kanazawa. Two Subhierarchies Inside the MCFLs.
Sylvain Salvati. MCFG and Higher Order Grammars.
Makoto Kanazawa. Pumping.
Sylvain Salvati. MIX.
Ryo Yoshinaka. Distributional Learning of Multiple Context-Free Grammars and Related Formalisms.

Makoto Kanazawa
kanazawa at nii

Last modified: 2011-10-19 19:46:36 JST