Weir, David (1992) A geometric hierarchy beyond context-free languages. Theoretical Computer Science, 104 (2). pp. 235-261. ISSN 0304-3975

Full text not available from this repository.

Abstract

This paper defines a geometric hierarchy of language classes the first member of which is context-free languages. This hierarchy generalizes the difference between context-free languages and the class of languages generated by four weakly equivalent grammar formalisms that are of interest to computational linguists. A grammatical characterization of the hierarchy is given using a variant of control grammars. Each member of the progression is shown to share many of the attractive features of context-free grammars, in particular, we show that each member is an abstract family of languages. We give a progression of automata and show that it corresponds exactly to the language hierarchy defined with control grammars.

Item Type:	Article
Schools and Departments:	School of Engineering and Informatics > Informatics
Subjects:	Q Science > QA Mathematics > QA0075 Electronic computers. Computer science P Language and Literature > P Philology. Linguistics
Depositing User:	David Weir
Date Deposited:	21 Nov 2006
Last Modified:	27 Aug 2019 15:14
URI:	http://sro.sussex.ac.uk/id/eprint/537
Google Scholar:	59 Citations

📧 Request an update