JetBrains Research unites scientists working in challenging new disciplines

Seminar on context-free path querying by matrix multiplication

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:

Presenter: Rustam Azimov

Date: September 25, 2017

Time: 17:15

Venue: room 3248, Faculty of Mathematics and Mechanics, Saint Petersburg State University, Stary Peterhof, Universitetski pr., 28