Standard

A recognition and parsing algorithm for arbitrary conjunctive grammars. / Okhotin, Alexander.

в: Theoretical Computer Science, Том 302, № 1-3, 13.06.2003, стр. 365-399.

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

Harvard

Okhotin, A 2003, 'A recognition and parsing algorithm for arbitrary conjunctive grammars', Theoretical Computer Science, Том. 302, № 1-3, стр. 365-399. https://doi.org/10.1016/S0304-3975(02)00853-8

APA

Okhotin, A. (2003). A recognition and parsing algorithm for arbitrary conjunctive grammars. Theoretical Computer Science, 302(1-3), 365-399. https://doi.org/10.1016/S0304-3975(02)00853-8

Vancouver

Okhotin A. A recognition and parsing algorithm for arbitrary conjunctive grammars. Theoretical Computer Science. 2003 Июнь 13;302(1-3):365-399. https://doi.org/10.1016/S0304-3975(02)00853-8

Author

Okhotin, Alexander. / A recognition and parsing algorithm for arbitrary conjunctive grammars. в: Theoretical Computer Science. 2003 ; Том 302, № 1-3. стр. 365-399.

BibTeX

@article{28aaf769b7e44a209ecabacb80d55342,
title = "A recognition and parsing algorithm for arbitrary conjunctive grammars",
abstract = "Conjunctive grammars are basically context-free grammars with an explicit set intersection operation added to the formalism of rules. This paper presents a cubic-time recognition and parsing algorithm for this family of grammars, which is applicable to an arbitrary conjunctive grammar without any initial transformations. The algorithm is in fact an extension of the context-free recognition and parsing algorithm due to Graham, Harrison and Ruzzo, and it retains the cubic time complexity of its prototype. It is shown that for the case of linear conjunctive grammars this algorithm can be modified to work in quadratic time and use linear space. The given algorithm is then applied to solve the membership problem for conjunctive grammars in polynomial time, and subsequently to prove the problem's P-completeness, as well as P-completeness of the membership problem for linear conjunctive grammars.",
keywords = "Complexity, Conjunctive grammars, Parsing, Recognition",
author = "Alexander Okhotin",
year = "2003",
month = jun,
day = "13",
doi = "10.1016/S0304-3975(02)00853-8",
language = "English",
volume = "302",
pages = "365--399",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-3",

}

RIS

TY - JOUR

T1 - A recognition and parsing algorithm for arbitrary conjunctive grammars

AU - Okhotin, Alexander

PY - 2003/6/13

Y1 - 2003/6/13

N2 - Conjunctive grammars are basically context-free grammars with an explicit set intersection operation added to the formalism of rules. This paper presents a cubic-time recognition and parsing algorithm for this family of grammars, which is applicable to an arbitrary conjunctive grammar without any initial transformations. The algorithm is in fact an extension of the context-free recognition and parsing algorithm due to Graham, Harrison and Ruzzo, and it retains the cubic time complexity of its prototype. It is shown that for the case of linear conjunctive grammars this algorithm can be modified to work in quadratic time and use linear space. The given algorithm is then applied to solve the membership problem for conjunctive grammars in polynomial time, and subsequently to prove the problem's P-completeness, as well as P-completeness of the membership problem for linear conjunctive grammars.

AB - Conjunctive grammars are basically context-free grammars with an explicit set intersection operation added to the formalism of rules. This paper presents a cubic-time recognition and parsing algorithm for this family of grammars, which is applicable to an arbitrary conjunctive grammar without any initial transformations. The algorithm is in fact an extension of the context-free recognition and parsing algorithm due to Graham, Harrison and Ruzzo, and it retains the cubic time complexity of its prototype. It is shown that for the case of linear conjunctive grammars this algorithm can be modified to work in quadratic time and use linear space. The given algorithm is then applied to solve the membership problem for conjunctive grammars in polynomial time, and subsequently to prove the problem's P-completeness, as well as P-completeness of the membership problem for linear conjunctive grammars.

KW - Complexity

KW - Conjunctive grammars

KW - Parsing

KW - Recognition

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

U2 - 10.1016/S0304-3975(02)00853-8

DO - 10.1016/S0304-3975(02)00853-8

M3 - Article

AN - SCOPUS:0037901023

VL - 302

SP - 365

EP - 399

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-3

ER -

ID: 41144914