Pregroup grammars with letter promotions: Complexity and context-freeness

We study pregroup grammars with letter promotions p(m)⇒q(n)p(m)⇒q(n). We show that the Letter Promotion Problem for pregroups is solvable in polynomial time, if the size of p(n)p(n) is counted as |n|+1|n|+1. In Mater and Fix (2005) [13], the problem is shown to be NP-hard, but their proof assumes the binary (or decimal, etc.) representation of n   in p(n)p(n), which seems less natural for applications. We reduce the problem to a graph-theoretic problem, which is subsequently reduced to the emptiness problem for context-free languages. As a consequence, the following problems are in P: the word problem for pregroups with letter promotions and the membership problem for pregroup grammars with letter promotions. We also prove that pregroup grammars with letter promotions are equivalent to context-free grammars. At the end, we obtain similar results for letter promotions with unit.

► We study pregroup grammars with letter promotions, i.e. additional assumptions of the form p(m)⇒q(n)p(m)⇒q(n), 1⇒p1⇒p, p⇒1p⇒1, generalizing Lambekʼs poset arrows p⇒qp⇒q (Lambek, 1999). ► We prove that the word problem for pregroups with letter promotions and the membership problem for the corresponding grammars are P, assuming the unary encoding of n   in p(n)p(n). The first problem was shown NP-hard, assuming the binary encoding (Mater and Fix, 2005). ► We prove that pregroup grammars with letter promotions recognize the context-free languages.