A1 Refereed original research article in a scientific journal

Linear-space recognition for grammars with contexts




AuthorsBarash, Mikhail; Okhotin, Alexander

PublisherELSEVIER SCIENCE BV

Publication year2018

Journal: Theoretical Computer Science

Journal name in sourceTHEORETICAL COMPUTER SCIENCE

Journal acronymTHEOR COMPUT SCI

Volume719

First page 73

Last page85

Number of pages13

ISSN0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2017.11.006

Web address https://www.sciencedirect.com/science/article/pii/S0304397517308368?via%3Dihub


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.



Last updated on 26/11/2025 01:39:59 PM