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

Tutkimustuotos: Lehtiartikkeli › Artikkeli › Tieteellinen › vertaisarvioitu

3 Sitaatiot (Scopus)

Abstrakti

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.

Alkuperäiskieli	Ei tiedossa
Sivut	73–85
Sivumäärä	13
Julkaisu	Theoretical Computer Science
Vuosikerta	719
DOI - pysyväislinkit	https://doi.org/10.1016/j.tcs.2017.11.006
Tila	Julkaistu - 2018
OKM-julkaisutyyppi	A1 Julkaistu artikkeli, soviteltu

Keywords

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

Pääsy asiakirjaan

10.1016/j.tcs.2017.11.006

Viittausmuodot

@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 -