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 [3], is a flexible and efficient computational device for parsing of natural languages. Buszkowski [2] 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 [1] 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.

References:

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.