Abstract
In [2], Bar-Hillel, Gaifman, and Shamir prove that the simple phrase structure grammars (SPGs) defined by Chomsky are equivalent in a certain sense to Bar-Hillel's bidirectional categorial grammars (BCGs). On the other hand, Cohen [3] proves the equivalence of the latter ones to what the calls free categorial grammars (FCGs). They are closely related to Lambek's syntactic calculus which, in turn, is based on the idea due to Ajdukiewicz [1]. For the reasons which will be discussed in the last section, Cohen's proof seems to be at least incomplete. This paper yields a direct proof of the equivalence ofFCGs andSPGs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Ajdukiewicz,Die Syntaktische Konnexität,Studia Philosophica 1 (1935), pp. 1–27.
Y. Bar-Hillel, C. Gaifman andE. Shamir,On Categorial and Phrase Structure Grammars,Bulletin of the Research Council of Israel 9F (1960) pp. 1–16.
J. M. Cohen,The Equivalence of Two Concepts of Categorial Grammar,Information and Control, 10 (1967), pp. 475–484.
J. Lambek,The Mathematics of Sentence Structure,American Mathematical Monthly 65 (1958), pp. 154–170.
Author information
Authors and Affiliations
Additional information
Allatum est die S Marlii 1976
Rights and permissions
About this article
Cite this article
Zielonka, W. A direct proof of the equivalence of free categorial grammars and simple phrase structure grammars. Stud Logica 37, 41–57 (1978). https://doi.org/10.1007/BF02123612
Issue Date:
DOI: https://doi.org/10.1007/BF02123612