The report will consider the problem of context-free path querying, as well as an algorithm for context-free path querying using matrix multiplication. In this problem, the input: an edge-labeled directed graph with symbols from some alphabet on the edges and some grammar over the same alphabet. It is required to find the paths in the input graph, such that labels on the edges form a word in the language specified by input grammar. The proposed algorithm solves this problem for CF grammars and does this by offloading the most intensive computations into calls to a Boolean matrix multiplication procedure. This algorithm based on the Valiant 's Context-free recognizer. In practice, the presented algorithm has an advantage over analogs due to the possibilities of efficient use of GPGPU and parallel computation.
Supplementary materials: https://github.com/YaccConstructor/articles/blob/master/InProgress/EDBT/graphparsing.pdf
Presenter: Rustam Azimov
Date: September 25, 2017
Venue: room 3248, Faculty of Mathematics and Mechanics, Saint Petersburg State University, Stary Peterhof, Universitetski pr., 28