Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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.
Original language | English |
---|---|
Title of host publication | CEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia |
Publisher | Association for Computing Machinery |
ISBN (Electronic) | 9781450363969 |
DOIs | |
State | Published - 20 Oct 2017 |
Event | 13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017 - Saint-Petersburg, Russian Federation Duration: 20 Oct 2017 → 21 Oct 2017 |
Name | ACM International Conference Proceeding Series |
---|
Conference | 13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017 |
---|---|
Country/Territory | Russian Federation |
City | Saint-Petersburg |
Period | 20/10/17 → 21/10/17 |
ID: 48535078