Non‐associative Lambek Categorial Grammar in Polynomial Time
Erik Aarts, Kees Trautwein · Mathematical logic quarterly · 1995
Abstract We present a new axiomatization of the non‐associative Lambek calculus. We prove that it takes polynomial time to reduce any non‐associative Lambek categorial grammar to an equivalent context‐free grammar. Since it is possible to recognize a sentence generated by a context‐free grammar in polynomial time, this proves that a sentence generated by any non‐associative Lambek categorial grammar can be recognized in polynomial time.