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.
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 | 273-282 |
| DOIs | |
| Publication status | Published - 2008 |
| Event | Third International Computer Science Symposium in Russia - Moscow, Russian Federation Duration: 7 Jun 2008 → 12 Jun 2008 Conference number: 3 https://link.springer.com/book/10.1007/978-3-540-79709-8 |
Conference
| Conference | Third International Computer Science Symposium in Russia |
|---|---|
| Abbreviated title | CSR 2008 |
| Country/Territory | Russian Federation |
| City | Moscow |
| Period | 7/06/08 → 12/06/08 |
| Internet address |