06102598

j

06102598 Buszkowski, Wojciech Lin, Zhe Moroz, Katarzyna Pregroup grammars with letter promotions: complexity and context-freeness. J. Comput. Syst. Sci. 78, No. 6, 1899-1909 (2012). 2012 Elsevier Science (Academic Press), San Diego, CA EN type grammar pregroup context-free grammar computational complexity

doi:10.1016/j.jcss.2011.12.010

Summary: We study pregroup grammars with letter promotions $p^{(m)}\Rightarrow q^{(n)}$. We show that the Letter Promotion Problem for pregroups is solvable in polynomial time, if the size of $p^{(n)}$ is counted as $|n|+1$. In [{\it A. H. Mater} and {\it J. D. Fix}, ``Finite presentations of pregroups and the identity problem'', in: Proceedings of the 10th conference on formal grammar and the 9th meeting on mathematics of language (FGMoL05), Edinburgh, August 2005. Stanford, CA: CSLI Publications. 63--72 (2005)], the problem is shown to be NP-hard, but their proof assumes the binary (or decimal, etc.) representation of $n$ in $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.