טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGenkin Daniel
SubjectRadical Lexicalization of Mildly Context-Sensitive
Languages
DepartmentDepartment of Computer Science
Supervisor Professor Michael Kaminski
Full Thesis textFull thesis text - English Version


Abstract

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   { an bn cn : n >0 } --- multiple agreement,

o   {am bn cm dn : 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.