Lambek Grammars with One Division Are Decidable in Polynomial Time

Yury Savateev

doi:10.1007/978-3-540-79709-8_28

Lambek Grammars with One Division Are Decidable in Polynomial Time

Yury Savateev

Research output: Contribution to conference › Paper › peer-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 language	English
Pages	273-282
DOIs	https://doi.org/10.1007/978-3-540-79709-8_28
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	https://link.springer.com/book/10.1007/978-3-540-79709-8

Access to Document

10.1007/978-3-540-79709-8_28

Cite this

@conference{8c0a7d3c9ef841c7b78cb91d82f379cb,

title = "Lambek Grammars with One Division Are Decidable in Polynomial Time",

abstract = "Lambek grammars provide a useful tool for studying formaland natural languages. The generative power of unidirectional Lambekgrammars equals that of context-free grammars. However, no feasible algorithm was known for deciding membership in the corresponding formallanguages. In this paper we present a polynomial algorithm for decidingwhether a given word belongs to a language generated by a given unidirectional Lambek grammar.",

author = "Yury Savateev",

year = "2008",

doi = "10.1007/978-3-540-79709-8_28",

language = "English",

pages = "273--282",

note = "Third International Computer Science Symposium in Russia, CSR 2008 ; Conference date: 07-06-2008 Through 12-06-2008",

url = "https://link.springer.com/book/10.1007/978-3-540-79709-8",

}

TY - CONF

T1 - Lambek Grammars with One Division Are Decidable in Polynomial Time

AU - Savateev, Yury

N1 - Conference code: 3

PY - 2008

Y1 - 2008

N2 - Lambek grammars provide a useful tool for studying formaland natural languages. The generative power of unidirectional Lambekgrammars equals that of context-free grammars. However, no feasible algorithm was known for deciding membership in the corresponding formallanguages. In this paper we present a polynomial algorithm for decidingwhether a given word belongs to a language generated by a given unidirectional Lambek grammar.

AB - Lambek grammars provide a useful tool for studying formaland natural languages. The generative power of unidirectional Lambekgrammars equals that of context-free grammars. However, no feasible algorithm was known for deciding membership in the corresponding formallanguages. In this paper we present a polynomial algorithm for decidingwhether a given word belongs to a language generated by a given unidirectional Lambek grammar.

U2 - 10.1007/978-3-540-79709-8_28

DO - 10.1007/978-3-540-79709-8_28

M3 - Paper

SP - 273

EP - 282

T2 - Third International Computer Science Symposium in Russia

Y2 - 7 June 2008 through 12 June 2008

ER -

Lambek Grammars with One Division Are Decidable in Polynomial Time

Abstract

Conference

Access to Document

Fingerprint

Cite this