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.

Язык оригиналаанглийский
Название основной публикацииCEE-SECR 2017 - Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia
ИздательAssociation for Computing Machinery
ISBN (электронное издание)9781450363969
DOI
СостояниеОпубликовано - 20 окт 2017
Событие13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017 - Saint-Petersburg, Российская Федерация
Продолжительность: 20 окт 201721 окт 2017

Серия публикаций

НазваниеACM International Conference Proceeding Series

конференция

конференция13th Central and Eastern European Software Engineering Conference in Russia, CEE-SECR 2017
Страна/TерриторияРоссийская Федерация
ГородSaint-Petersburg
Период20/10/1721/10/17

    Предметные области Scopus

  • Программный продукт
  • Человеко-машинное взаимодействие
  • Компьютерное зрение и распознавание образов
  • Компьютерные сети и коммуникации

ID: 48535078