M.Sc Student | Genkin Daniel |
---|---|

Subject | Radical Lexicalization of Mildly Context-Sensitive Languages |

Department | Department of Computer Science |

Supervisor | Professor Michael Kaminski |

Full Thesis text |

A family of languages is called mildly context-sensitive if

? it includes the family of all ε-free context-free languages;

? it contains the languages

o { a^{n}
b^{n} c^{n} : n >0 } --- multiple agreement,

o {a^{m} b^{n}
c^{m} d^{n} : m,n > 0 } --- crossed dependencies,

o { ww : w ∈ Σ^{} } --- reduplication;

? all its languages are semi-linear; and

? their membership problem is decidable in polynomial time.

In this thesis we introduce a new model of computation called buffer augmented pregroup grammars that defines a family of mildly context-sensitive languages.

This model of computation is an extension of Lambek pregroup grammars with a variable symbol--- the buffer and is allowed to make an arbitrary substitution from the original pregroup to the variable.

This increases the pregroup grammar generation power, but still retains the desired properties of mildly context-sensitive languages such as semi-linearity and polynomial parsing.

We establish a strict hierarchy within the family of mildly context-sensitive languages defined by buffer augmented pregroup grammars.

In this hierarchy, the hierarchy level of the family language depends on the allowed number of occurrences of the variable in

lexical category assignments.

We also present an automaton counterpart of buffer augmented pregroup grammars, called buffer augmented pushdown automata and prove that a language is generated by a buffer augmented pregroup grammar if and only if it is accepted by a buffer augmented pushdown automaton.