Standard

Two-sided context specifications in formal grammars. / Barash, Mikhail; Okhotin, Alexander.

In: Theoretical Computer Science, Vol. 591, 02.08.2015, p. 134-153.

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

Harvard

Barash, M & Okhotin, A 2015, 'Two-sided context specifications in formal grammars', Theoretical Computer Science, vol. 591, pp. 134-153. https://doi.org/10.1016/j.tcs.2015.05.004

APA

Barash, M., & Okhotin, A. (2015). Two-sided context specifications in formal grammars. Theoretical Computer Science, 591, 134-153. https://doi.org/10.1016/j.tcs.2015.05.004

Vancouver

Barash M, Okhotin A. Two-sided context specifications in formal grammars. Theoretical Computer Science. 2015 Aug 2;591:134-153. https://doi.org/10.1016/j.tcs.2015.05.004

Author

Barash, Mikhail ; Okhotin, Alexander. / Two-sided context specifications in formal grammars. In: Theoretical Computer Science. 2015 ; Vol. 591. pp. 134-153.

BibTeX

@article{0bd778c21a6e4132af0aee81a128a8a1,
title = "Two-sided context specifications in formal grammars",
abstract = "In a recent paper (M. Barash, A. Okhotin, {"}An extension of context-free grammars with one-sided context specifications{"}, Inform. and Comput., 2014), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O(n4), where n is the length of the input string.",
keywords = "Conjunctive grammars, Context-free grammars, Context-sensitive grammars, Grammars with contexts, Parsing",
author = "Mikhail Barash and Alexander Okhotin",
year = "2015",
month = aug,
day = "2",
doi = "10.1016/j.tcs.2015.05.004",
language = "English",
volume = "591",
pages = "134--153",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Two-sided context specifications in formal grammars

AU - Barash, Mikhail

AU - Okhotin, Alexander

PY - 2015/8/2

Y1 - 2015/8/2

N2 - In a recent paper (M. Barash, A. Okhotin, "An extension of context-free grammars with one-sided context specifications", Inform. and Comput., 2014), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O(n4), where n is the length of the input string.

AB - In a recent paper (M. Barash, A. Okhotin, "An extension of context-free grammars with one-sided context specifications", Inform. and Comput., 2014), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O(n4), where n is the length of the input string.

KW - Conjunctive grammars

KW - Context-free grammars

KW - Context-sensitive grammars

KW - Grammars with contexts

KW - Parsing

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

U2 - 10.1016/j.tcs.2015.05.004

DO - 10.1016/j.tcs.2015.05.004

M3 - Article

AN - SCOPUS:84943659952

VL - 591

SP - 134

EP - 153

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 41139338