Linguistic Analysis

A research journal devoted to the publication of high quality articles in formal phonology, morphology, syntax and semantics. In continuous publication since 1976. ISSN: 0098-9053


Polynomial Pregroup Grammars Parse Context Sensitive Languages

Pregroup grammars with a possibly infinite number of lexical 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 sensitive natural language fragments of Dutch, Swiss-German or Old Georgian. A polynomial recognition and parsing algorithm handles the various grammars uniformly. It also computes a planar graph for the semantic cross-serial dependencies in the case of natural languages.