The equivalence of four extensions of context-free grammars

Vijay-Shanker, K. and Weir, David (1994) The equivalence of four extensions of context-free grammars. Mathematical Systems Theory / Theory of Computer Systems, 27 (6). pp. 511-546. ISSN 1432-4350

Download (370kB) | Preview


There is currently considerable interest among computational linguists in grammatical formalisms with highly restricted generative power. This paper concerns the relationship between the class of string languages generated by several such formalisms, namely, combinatory categorial grammars, head grammars, linear indexed grammars, and tree adjoining grammars. Each of these formalisms is known to generate a larger class of languages than context-free grammars. The four formalisms under consideration were developed independently and appear superficially to be quite different from one another. The result presented in this paper is that all four of the formalisms under consideration generate exactly the same class of string languages.

Item Type: Article
Schools and Departments: School of Engineering and Informatics > Informatics
Subjects: Q Science > QA Mathematics > QA0075 Electronic computers. Computer science
Depositing User: David Weir
Date Deposited: 21 Nov 2006
Last Modified: 27 Aug 2019 11:39
Google Scholar:198 Citations

View download statistics for this item

📧 Request an update