Екатерина Шеметова

Екатерина Шеметова


Исследовательские группы

Биография

Екатерина получила степень магистра в области разработки программного обеспечения в Университете ИТМО. В настоящее время является аспирантом по направлению "Информатика и вычислительная техника" в Санкт-Петербургском Академическом университете.

Области научных интересов: теория формальных языков и её приложения, статический анализ кода, информационная безопасность, теория сложности вычислений.

Публикации

Path querying on acyclic graphs using Boolean grammars

January 2019

Shemetova E.N., Grigorev S.V.

One of the problems in graph data analysis is querying for specific paths. Such queries are usually performed by means of a formal grammar that describes the allowed edge-labeling of the paths. Path query is said to be calculated using relational query semantics if it is evaluated to triple ((A,v1,v2), such that there is a path from v1 to v2 such that the labels on the edges of this path form a string derivable from the nonterminal A. We focus on the Boolean languages that use Boolean grammars to describe the labeling of paths. Although path querying using relational query semantics and Boolean grammars is known to be undecidable, in this work we propose a path querying algorithm on acyclic graphs which uses relational query semantics and Boolean grammars and approximates the exact solution. To achieve better performance in compare with the naive algorithm, considered classes of graphs were limited to acyclic graphs.

Proceedings of the Institute for System Programming

Подробнее