Linear-space recognition for grammars with contexts

Mikhail Barash; A Okhotin

doi:10.1016/j.tcs.2017.11.006

Linear-space recognition for grammars with contexts

Mikhail Barash, A Okhotin

Research output: Contribution to journal › Article › Scientific › peer-review

2 Citations (Scopus)

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. (C) 2017 Elsevier By. All rights reserved.

Original language	Undefined/Unknown
Pages (from-to)	73–85
Number of pages	13
Journal	Theoretical Computer Science
Volume	719
DOIs	https://doi.org/10.1016/j.tcs.2017.11.006
Publication status	Published - 2018
MoE publication type	A1 Journal article-refereed

Keywords

Context-free grammars
Conjunctive grammars
Context-sensitive grammars
Space complexity
Parsing

Access to Document

10.1016/j.tcs.2017.11.006

Cite this

@article{ac34cc86982b47c19c3f4aaad1695900,

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. (C) 2017 Elsevier By. All rights reserved.",

keywords = "Context-free grammars, Conjunctive grammars, Context-sensitive grammars, Space complexity, Parsing, Context-free grammars, Conjunctive grammars, Context-sensitive grammars, Space complexity, Parsing, Context-free grammars, Conjunctive grammars, Context-sensitive grammars, Space complexity, Parsing",

author = "Mikhail Barash and A Okhotin",

year = "2018",

doi = "10.1016/j.tcs.2017.11.006",

language = "Odefinierat/ok{\"a}nt",

volume = "719",

pages = "73–85",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Linear-space recognition for grammars with contexts

AU - Barash, Mikhail

AU - Okhotin, A

PY - 2018

Y1 - 2018

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. (C) 2017 Elsevier By. All rights reserved.

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. (C) 2017 Elsevier By. All rights reserved.

KW - Context-free grammars

KW - Conjunctive grammars

KW - Context-sensitive grammars

KW - Space complexity

KW - Parsing

KW - Context-free grammars

KW - Conjunctive grammars

KW - Context-sensitive grammars

KW - Space complexity

KW - Parsing

KW - Context-free grammars

KW - Conjunctive grammars

KW - Context-sensitive grammars

KW - Space complexity

KW - Parsing

U2 - 10.1016/j.tcs.2017.11.006

DO - 10.1016/j.tcs.2017.11.006

M3 - Artikel

SN - 0304-3975

VL - 719

SP - 73

EP - 85

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -