✦ LIBER ✦
Non-associative Lambek Categorial Grammar in Polynomial Time
✍ Scribed by Erik Aarts; Kees Trautwein
- Publisher
- John Wiley and Sons
- Year
- 1995
- Tongue
- English
- Weight
- 455 KB
- Volume
- 41
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
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.