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

Åbo datatekniska forsknings- och utbildningscentrum (TUCS)

Forskningsoutput: Tidskriftsbidrag › Artikel › Vetenskaplig › Peer review

2 Citeringar (Scopus)

Sammanfattning

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.

Originalspråk	Odefinierat/okänt
Sidor (från-till)	73–85
Antal sidor	13
Tidskrift	Theoretical Computer Science
Volym	719
DOI	https://doi.org/10.1016/j.tcs.2017.11.006
Status	Publicerad - 2018
MoE-publikationstyp	A1 Tidskriftsartikel-refererad

Nyckelord

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

Åtkomst av dokument

10.1016/j.tcs.2017.11.006

Citera det här

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