Product-free Lambek calculus and context-free grammars

Journal of Symbolic Logic 62 (2):648-660 (1997)
  Copy   BIBTEX

Abstract

In this paper we prove the Chomsky Conjecture (all languages recognized by the Lambek calculus are context-free) for both the full Lambek calculus and its product-free fragment. For the latter case we present a construction of context-free grammars involving only product-free types

Categories

Keywords

Reprint years

DOI

10.2307/2275553

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,475

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Gaifman's theorem on categorial grammars revisited.Wojciech Buszkowski - 1988 - Studia Logica 47 (1):23 - 33.
Linear axiomatics of commutative product-free Lambek calculus.Wojciech Zielonka - 1990 - Studia Logica 49 (4):515 - 522.
The finite model property for BCI and related systems.Wojciech Buszkowski - 1996 - Studia Logica 57 (2-3):303 - 323.
On reduction systems equivalent to the Lambek calculus with the empty string.Wojciech Zielonka - 2002 - Studia Logica 71 (1):31-46.
The Lambek calculus enriched with additional connectives.Makoto Kanazawa - 1992 - Journal of Logic, Language and Information 1 (2):141-171.
On the expressive power of abstract categorial grammars: Representing context-free formalisms. [REVIEW]Philippe de Groote & Sylvain Pogodalla - 2004 - Journal of Logic, Language and Information 13 (4):421-438.
A simple and general method of solving the finite axiomatizability problems for Lambek's syntactic calculi.Wojciech Zielonka - 1989 - Studia Logica 48 (1):35 - 39.
A direct proof of the equivalence of free categorial grammars and simple phrase structure grammars.Wojciech Zielonka - 1978 - Studia Logica 37 (1):41 - 57.

Analytics

Added to PP
2009-01-28

Downloads
50 (#315,384)

6 months
15 (#162,849)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

On the Recognizing Power of the Lambek Calculus with Brackets.Makoto Kanazawa - 2018 - Journal of Logic, Language and Information 27 (4):295-312.
Linguistic applications of first order intuitionistic linear logic.Richard Moot & Mario Piazza - 2001 - Journal of Logic, Language and Information 10 (2):211-232.
Computing interpolants in implicational logics.Makoto Kanazawa - 2006 - Annals of Pure and Applied Logic 142 (1):125-201.

View all 6 citations / Add more citations

References found in this work

Language in action.Johan Van Benthem - 1991 - Journal of Philosophical Logic 20 (3):225-263.
The Equivalence of Unidirectional Lambek Categorial Grammars and Context-Free Grammars.Wojcßch Buszkowski - 1985 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 31 (24):369-384.

Add more references