Unidirectional Lambek Grammars in Polynomial Time

Yury Savateev

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)662-672
JournalTheory of Computing Systems
Volume46
DOIs
Publication statusPublished - 28 Mar 2009

Keywords

  • Lambek calculus
  • Unidirectional Lambek grammars
  • complexity

Fingerprint

Dive into the research topics of 'Unidirectional Lambek Grammars in Polynomial Time'. Together they form a unique fingerprint.

Cite this