Unidirectional Lambek Grammars in Polynomial Time

Yury Savateev

doi:10.1007/s00224-009-9208-4

Unidirectional Lambek Grammars in Polynomial Time

Yury Savateev

Research output: Contribution to journal › Article › peer-review

10 Citations (Scopus)

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	https://doi.org/10.1007/s00224-009-9208-4
Publication status	Published - 28 Mar 2009

Keywords

Lambek calculus
Unidirectional Lambek grammars
complexity

Access to Document

10.1007/s00224-009-9208-4

Cite this

@article{813c23ba43d346449a0b5d4da905b789,

title = "Unidirectional Lambek Grammars in Polynomial Time",

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.",

keywords = "Lambek calculus, Unidirectional Lambek grammars, complexity",

author = "Yury Savateev",

year = "2009",

month = mar,

day = "28",

doi = "10.1007/s00224-009-9208-4",

language = "English",

volume = "46",

pages = "662--672",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer Nature ",

}

TY - JOUR

T1 - Unidirectional Lambek Grammars in Polynomial Time

AU - Savateev, Yury

PY - 2009/3/28

Y1 - 2009/3/28

N2 - 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.

AB - 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.

KW - Lambek calculus

KW - Unidirectional Lambek grammars

KW - complexity

U2 - 10.1007/s00224-009-9208-4

DO - 10.1007/s00224-009-9208-4

M3 - Article

SN - 1432-4350

VL - 46

SP - 662

EP - 672

JO - Theory of Computing Systems

JF - Theory of Computing Systems

ER -

Unidirectional Lambek Grammars in Polynomial Time

Abstract

Keywords

Access to Document

Fingerprint

Cite this