Linear-space recognition for grammars with contexts

Mikhail Barash, Alexander Okhotin

Результат исследований: Научные публикации в периодических изданияхстатья

1 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)73-85
Число страниц13
ЖурналTheoretical Computer Science
Том719
DOI
СостояниеОпубликовано - 6 апр 2018

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Linear-space recognition for grammars with contexts». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать