zbMATH — the first resource for mathematics

Lambek grammars with one division are decidable in polynomial time. (English) Zbl 1142.68415
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 273-282 (2008).
Summary: 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.
For the entire collection see [Zbl 1136.68005].

68Q42 Grammars and rewriting systems
03B25 Decidability of theories and sets of sentences
03B65 Logic of natural languages
Full Text: DOI