Abstract
Lambek grammars provide a useful tool for studying formal and natural languages. The generative power of unidirectional Lambek grammars equals that of context-free grammars. However, no feasible algorithm was known for deciding membership in the corresponding formal languages. In this paper we present a polynomial algorithm for deciding whether a given word belongs to a language generated by a given unidirectional Lambek grammar.
Original language | English |
---|---|
Pages (from-to) | 662-672 |
Journal | Theory of Computing Systems |
Volume | 46 |
DOIs | |
Publication status | Published - 28 Mar 2009 |
Keywords
- Lambek calculus
- Unidirectional Lambek grammars
- complexity