S.-Y. Kuroda Prize 2013

The SIGMOL S.-Y. Kuroda Prize, in its inaugural year, is awarded (ex aequo) to Aravind K. Joshi (University of Pennsylvania), Vijay K. Shanker (University of Delaware), and David Weir (University of Sussex).

Tree-Adjoining Grammar (TAG), defined by Aravind Joshi, Leon Levy, and Masako Takahashi in the mid−70s, was the first known formalism that was powerful enough to capture the sorts of constraints linguists used in describing syntax, but weak enough to be computationally tractable. Work by Joshi and Anthony Kroch, along with their myriads of students, established the value of TAGs both for computational linguistics proper (theorizing about the structure of language) and for natural language processing. Today there are wide-coverage TAG grammars for a wide variety of languages which are employed in a even wider range of applications.

In the mid−80s, Joshi’s students Vijay Shanker and David Weir discovered that TAGs are equivalent, in weak generative capacity, to the Head Grammars of Carl Pollard. This led to a rapid succession of similar results establishing the weak equivalence of most of the practical properly context−sensitive formalisms that were known at the time—a unifying result that was as unexpected as it was broadly encompassing. The subsequent generalization, the Linear Context Free Rewriting Systems (LCFRSs), subsumes not only most of the extensions of TAG that were known at the time, but a wide range of formalisms that have been independently proposed since then, including Minimalist Grammars, Multiple Context−Free grammars, and a variety of categorial grammars.

This unified class of formal languages, termed the “mildly context−sensitive languages”, has become the benchmark for practical formalisms that are useful in describing natural language syntax. The territory that was opened by the work of Joshi, Shanker, and Weir has fostered an enormous body of research in computational linguistics and natural language processing, and has sustained a community of researchers that goes far beyond the direct academic descendants of the three researchers whose work is now honored with this prize.

Official Citation