Linear-space recognition for grammars with contexts

Mikhail Barash, A Okhotin

    Research output: Contribution to journalArticleScientificpeer-review

    2 Citations (Scopus)

    Abstract

    Grammars with contexts are an extension of context-free grammars equipped with operators for referring to the left and the right contexts of a substring being defined. These grammars are notable for still having a cubic-time parsing algorithm, as well as for being able to describe some useful syntactic constructs, such as declaration before use. It is proved in this paper that every language described by a grammar with contexts can be recognized in deterministic linear space. (C) 2017 Elsevier By. All rights reserved.
    Original languageUndefined/Unknown
    Pages (from-to)73–85
    Number of pages13
    JournalTheoretical Computer Science
    Volume719
    DOIs
    Publication statusPublished - 2018
    MoE publication typeA1 Journal article-refereed

    Keywords

    • Context-free grammars
    • Conjunctive grammars
    • Context-sensitive grammars
    • Space complexity
    • Parsing

    Cite this