Standard

Linear-space recognition for grammars with contexts. / Barash, Mikhail; Okhotin, Alexander.

в: Theoretical Computer Science, Том 719, 06.04.2018, стр. 73-85.

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

Harvard

Barash, M & Okhotin, A 2018, 'Linear-space recognition for grammars with contexts', Theoretical Computer Science, Том. 719, стр. 73-85. https://doi.org/10.1016/j.tcs.2017.11.006

APA

Barash, M., & Okhotin, A. (2018). Linear-space recognition for grammars with contexts. Theoretical Computer Science, 719, 73-85. https://doi.org/10.1016/j.tcs.2017.11.006

Vancouver

Barash M, Okhotin A. Linear-space recognition for grammars with contexts. Theoretical Computer Science. 2018 Апр. 6;719:73-85. https://doi.org/10.1016/j.tcs.2017.11.006

Author

Barash, Mikhail ; Okhotin, Alexander. / Linear-space recognition for grammars with contexts. в: Theoretical Computer Science. 2018 ; Том 719. стр. 73-85.

BibTeX

@article{cd6338b2cc8141bf8141bd29b7cabb3c,
title = "Linear-space recognition for grammars with contexts",
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.",
keywords = "Conjunctive grammars, Context-free grammars, Context-sensitive grammars, Parsing, Space complexity, SPECIFICATIONS, BOOLEAN GRAMMARS, COMPLEXITY, ONE-SIDED CONTEXTS, TRELLIS AUTOMATA, TIME",
author = "Mikhail Barash and Alexander Okhotin",
year = "2018",
month = apr,
day = "6",
doi = "10.1016/j.tcs.2017.11.006",
language = "English",
volume = "719",
pages = "73--85",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Linear-space recognition for grammars with contexts

AU - Barash, Mikhail

AU - Okhotin, Alexander

PY - 2018/4/6

Y1 - 2018/4/6

N2 - 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.

AB - 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.

KW - Conjunctive grammars

KW - Context-free grammars

KW - Context-sensitive grammars

KW - Parsing

KW - Space complexity

KW - SPECIFICATIONS

KW - BOOLEAN GRAMMARS

KW - COMPLEXITY

KW - ONE-SIDED CONTEXTS

KW - TRELLIS AUTOMATA

KW - TIME

UR - http://www.scopus.com/inward/record.url?scp=85035206819&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2017.11.006

DO - 10.1016/j.tcs.2017.11.006

M3 - Article

AN - SCOPUS:85035206819

VL - 719

SP - 73

EP - 85

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 33856828