A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Linear-space recognition for grammars with contexts




TekijätBarash, Mikhail; Okhotin, Alexander

KustantajaELSEVIER SCIENCE BV

Julkaisuvuosi2018

Lehti: Theoretical Computer Science

Tietokannassa oleva lehden nimiTHEORETICAL COMPUTER SCIENCE

Lehden akronyymiTHEOR COMPUT SCI

Vuosikerta719

Aloitussivu73

Lopetussivu85

Sivujen määrä13

ISSN0304-3975

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

Verkko-osoitehttps://www.sciencedirect.com/science/article/pii/S0304397517308368?via%3Dihub


Tiivistelmä

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