Standard

Context-free path querying with structural representation of result. / Grigorev, Semyon; Ragozina, Anastasiya.

CEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia. Association for Computing Machinery, 2017. 3166104 (ACM International Conference Proceeding Series).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Grigorev, S & Ragozina, A 2017, Context-free path querying with structural representation of result. in CEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia., 3166104, ACM International Conference Proceeding Series, Association for Computing Machinery, 13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017, Saint-Petersburg, Russian Federation, 20/10/17. https://doi.org/10.1145/3166094.3166104

APA

Grigorev, S., & Ragozina, A. (2017). Context-free path querying with structural representation of result. In CEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia [3166104] (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3166094.3166104

Vancouver

Grigorev S, Ragozina A. Context-free path querying with structural representation of result. In CEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia. Association for Computing Machinery. 2017. 3166104. (ACM International Conference Proceeding Series). https://doi.org/10.1145/3166094.3166104

Author

Grigorev, Semyon ; Ragozina, Anastasiya. / Context-free path querying with structural representation of result. CEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia. Association for Computing Machinery, 2017. (ACM International Conference Proceeding Series).

BibTeX

@inproceedings{55dfb54c850a4035be02314a3e0cee38,
title = "Context-free path querying with structural representation of result",
abstract = "Graph data model and graph databases are popular in such areas as bioinformatics, semantic web, and social networks. One specific problem in the area is a path querying with constraints formulated in terms of formal grammars. The query in this approach is written as a grammar and paths querying is graph parsing with respect to the grammar. There are several solutions to it, but they are based mostly on CYK or Earley algorithms which impose some restrictions in comparison with other parsing techniques, and employing of advanced parsing techniques for graph parsing is still an open problem. In this paper we propose a graph parsing technique which is based on generalized top-down parsing algorithm (GLL) and allows one to build finite structural query result representation with respect to the given grammar in polynomial time and space for arbitrary context-free grammar and graph.",
keywords = "CFPQ, Context-free grammar, GLL, Graph database, Graph parsing, LL, Path query, Top-down parsing",
author = "Semyon Grigorev and Anastasiya Ragozina",
year = "2017",
month = oct,
day = "20",
doi = "10.1145/3166094.3166104",
language = "English",
series = "ACM International Conference Proceeding Series",
publisher = "Association for Computing Machinery",
booktitle = "CEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia",
address = "United States",
note = "13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017 ; Conference date: 20-10-2017 Through 21-10-2017",

}

RIS

TY - GEN

T1 - Context-free path querying with structural representation of result

AU - Grigorev, Semyon

AU - Ragozina, Anastasiya

PY - 2017/10/20

Y1 - 2017/10/20

N2 - Graph data model and graph databases are popular in such areas as bioinformatics, semantic web, and social networks. One specific problem in the area is a path querying with constraints formulated in terms of formal grammars. The query in this approach is written as a grammar and paths querying is graph parsing with respect to the grammar. There are several solutions to it, but they are based mostly on CYK or Earley algorithms which impose some restrictions in comparison with other parsing techniques, and employing of advanced parsing techniques for graph parsing is still an open problem. In this paper we propose a graph parsing technique which is based on generalized top-down parsing algorithm (GLL) and allows one to build finite structural query result representation with respect to the given grammar in polynomial time and space for arbitrary context-free grammar and graph.

AB - Graph data model and graph databases are popular in such areas as bioinformatics, semantic web, and social networks. One specific problem in the area is a path querying with constraints formulated in terms of formal grammars. The query in this approach is written as a grammar and paths querying is graph parsing with respect to the grammar. There are several solutions to it, but they are based mostly on CYK or Earley algorithms which impose some restrictions in comparison with other parsing techniques, and employing of advanced parsing techniques for graph parsing is still an open problem. In this paper we propose a graph parsing technique which is based on generalized top-down parsing algorithm (GLL) and allows one to build finite structural query result representation with respect to the given grammar in polynomial time and space for arbitrary context-free grammar and graph.

KW - CFPQ

KW - Context-free grammar

KW - GLL

KW - Graph database

KW - Graph parsing

KW - LL

KW - Path query

KW - Top-down parsing

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

U2 - 10.1145/3166094.3166104

DO - 10.1145/3166094.3166104

M3 - Conference contribution

AN - SCOPUS:85041122514

T3 - ACM International Conference Proceeding Series

BT - CEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia

PB - Association for Computing Machinery

T2 - 13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017

Y2 - 20 October 2017 through 21 October 2017

ER -

ID: 48535078