Gijs Wijnholds
(ILLC)
Conversions between D and MCFG_wn: Logical characterizations of the Mildly Context-Sensitive Languages
February 21st at 17:30, in ILLC Seminar Room (F1.15)
Formal Grammar regained interest in the 80s when it was recognized that Context Free Grammar was too poor a formalism for natural language. Extensions were proposed, both on the side of transformational grammar as on the side of categorial grammar. In 1985, Joshi proposed a new class of languages, the so-called Mildly Context-Sensitive Languages, and showed that his Tree Adjoining Grammars describe a subclass of the MCSL. Even though there are several extensions of the Lambek Calculus in existence today, not much is known about their generative capacity. We show that two variants of the general Displacement Calculus, originating from the work of Morrill in the 90s, are weakly equivalent to (i.e. describe the same string languages) well-nested Multiple Context Free Grammar, a tuple-based extension of Context Free Grammar coming from Seki et al. and further studied by Kanazawa. Because well-nested MCFGs describe the Mildly Context-Sensitive Languages, the result therefore gives us two logical characterizations of the Mildly Context-Sensitive Languages.
We will start with a brief introduction to the domain of Formal Grammar by introducing Context-Free Grammar and the Lambek Calculus, and stating the (extended) Chomsky Hierarchy. We then go on to define the involved extensions (that is, MCFG and Displacement Calculus) and show how to restrict the systems to obtain an equivalence of string languages.