DOI

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 languageEnglish
Title of host publicationCEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450363969
DOIs
StatePublished - 20 Oct 2017
Event13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017 - Saint-Petersburg, Russian Federation
Duration: 20 Oct 201721 Oct 2017

Publication series

NameACM International Conference Proceeding Series

Conference

Conference13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017
Country/TerritoryRussian Federation
CitySaint-Petersburg
Period20/10/1721/10/17

    Research areas

  • CFPQ, Context-free grammar, GLL, Graph database, Graph parsing, LL, Path query, Top-down parsing

    Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

ID: 48535078