✦ LIBER ✦

Extending Lambek grammars to basic categorial grammars

✍ Scribed by Wojciech Buszkowski

Publisher: Springer Netherlands
Year: 1996
Tongue: English
Weight: 931 KB
Volume: 5
Category: Article
ISSN: 0925-8531
DOI: 10.1007/bf00159342

No coin nor oath required. For personal study only.

✦ Synopsis

Pentus (1992)

proves the equivalence of LCG's and CFG's, and CFG's are equivalent to BCG's by the Gaifman theorem (Bar-Hillel et al., 1960). This paper provides a procedure to extend any LCG to an equivalent BCG by affixing new types to the lexicon; a procedure of that kind was proposed as early, as Cohen ( 1967), but it was deficient (Buszkowski, 1985). We use a modification of Pentus' proof and a new proof of the Gaifman theorem on the basis of the Lambek calculus.

📜 SIMILAR VOLUMES

Stochastic Lambek Categorial Grammars

✍ Guillaume Bonfante; Philippe de Groote 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 407 KB

The Equivalence of Unidirectional Lambek

The Equivalence of Unidirectional Lambek Categorial Grammars and Context-Free Grammars

✍ Wojcßch Buszkowski 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 1004 KB

The equivalence of Nonassociative Lambek

The equivalence of Nonassociative Lambek Categorial Grammars and Context-Free Grammars

✍ Maciej Kandulski 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 699 KB

Besides this introduction the paper contains four sections. I n section 1 we describe three equivalent axiomatizations of NLP. the third one playing important role in what follows. I n section 2 we deal with a system AC: (the Ajdukiewicz calculus with product) and prove the equivalence of AC-grammar

A Faithful Representation of Non-Associa

A Faithful Representation of Non-Associative Lambek Grammars in Abstract Categorial Grammars

✍ Christian Retoré; Sylvain Salvati 📂 Article 📅 2010 🏛 Springer Netherlands 🌐 English ⚖ 356 KB

Non-associative Lambek Categorial Gramma

Non-associative Lambek Categorial Grammar in Polynomial Time

✍ Erik Aarts; Kees Trautwein 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 455 KB

We present a new axiomatization of the non-associative Lambek calculus. We prove that it takes polynomial time to reduce any non-associative Lambek categorial grammar to an equivalent context-free grammar. Since it is possible to recognize a sentence generated by a context-free grammar in polynomial

The emptiness of intersection problem fo

The emptiness of intersection problem for languages of k-valued categorial grammars (classical and Lambek) is undecidable

✍ Annie Foret 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 465 KB

This paper is concerned with usual decidability questions on grammars for some classes of categorial grammars that arise in the field of learning categorial grammars. We prove that the emptiness of intersection of two langages is an undecidable problem for the following classes : k-valued classical