Ekaterina Shemetova

Ekaterina Shemetova

Research Groups


Ekaterina got master’s degree in Software Engineering from Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics (ITMO University) in 2019. Currently, Ekaterina is a postgraduate student in Information Technology at the Saint-Petersburg Academic University.

Her research interests include formal language theory and applications, static code analysis, information security and computational complexity theory.


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

Read more