A1 Refereed original research article in a scientific journal
Linear-space recognition for grammars with contexts
Authors: Barash, Mikhail; Okhotin, Alexander
Publisher: ELSEVIER SCIENCE BV
Publication year: 2018
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 719
First page : 73
Last page: 85
Number of pages: 13
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2017.11.006
Web address : https://www.sciencedirect.com/science/article/pii/S0304397517308368?via%3Dihub
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.