University of Sussex
Browse

File(s) not publicly available

A geometric hierarchy beyond context-free languages

journal contribution
posted on 2023-06-07, 13:30 authored by David WeirDavid Weir
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.

History

Publication status

  • Published

Journal

Theoretical Computer Science

ISSN

0304-3975

Issue

2

Volume

104

Page range

235-261

Department affiliated with

  • Informatics Publications

Full text available

  • No

Peer reviewed?

  • No

Legacy Posted Date

2006-11-21

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC