PTIME transformation of pregroup grammar into CFG and PDA
Wojciech Buszkowski and Katarzyna Moroz (Adam Mickiewicz University, Poznań)
We present a direct construction of a context-free grammar equivalent to a given pregroup grammar. The construction can be performed in a polynomial time.
The calculus of pregroups, introduced by Lambek , is a flexible and efficient computational device for parsing of natural languages. Buszkowski  proves the equivalence of pregroup grammars and context-free grammars. The proof uses the fact that context-free languages are closed under homomorfic coimages and images. We show that, according to these lines, one obtains a PTIME transformation of a pregroup grammar.
Our construction improves the results of Bechet  who provides a construction requiring an expotential time.
We also present a direct PTIME construction of a push-down automaton for a given pregroup grammar.
1. D. Bechet, Parsing pregroup grammars and Lambek calculus using partial composition, manuscript (to appear).
2. W. Buszkowski, Lambek Grammars Based on Pregroups, in: P. de Groote, G.Morrill, C.Retore (Eds.): LACL 2001, LNAI 2099, pp. 95-109, 2001.
3. J. Lambek, Type grammars as pregroups, Grammars 4, (2001), 21-39.