Polynomial Pregroup Grammars parse Context Sensitive Languages

Journal verion of research report lirmm-00412876 ; International audience ; Pregroup grammars with a possibly infinite number of lexi- cal entries are polynomial if the length of type assignments for sentences is a polynomial in the number of words. Polynomial pregroup grammars are shown to generate the standard mildly context sensitive formal languages as well as some context sensi- tive natural language fragments of Dutch, Swiss-German or Old Georgian. A polynomial recognition and parsing algorithm han- dles the various grammars uniformly. It also computes a planar graph for the semantic cro... Mehr ...