Ekaterina Shemetova
Biography
Ekaterina got master’s degree in Software Engineering from SaintPetersburg National Research University of Information Technologies, Mechanics and Optics (ITMO University) in 2019. Currently, Ekaterina is a postgraduate student in Information Technology at the SaintPetersburg Academic University.
Her research interests include formal language theory and applications, static code analysis, information security and computational complexity theory.
Projects

Space for contextfree path querying algorithms research and development.Project supervisor: Semyon Grigorev
Publications

Proceedings of the Institute for System Programming, January 2019
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 edgelabeling 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.

Programming Languages and Tools Lab Researcher
 Formal Languages and Syntax Analysis