A geometric hierarchy beyond context-free languages

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.


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