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
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.