JetBrains Research is a private enterprise created to unite scientific projects that really make a difference and strive to improve a current state of science and technology. With the support of JetBrains, researchers and teams can focus on the actual work, instead of grant seeking or dealing with other management issues.
Programming and Computer Software,
Path querying with conjunctive grammars is known to be undecidable. There is an algorithm for path querying with linear conjunctive grammars which provides an over-approximation of the result, but there is no algorithm for arbitrary conjunctive grammars. We propose the first algorithm for path querying with arbitrary conjunctive grammars. The proposed algorithm is matrix-based and allows us to efficiently apply GPGPU computing techniques and other optimizations for matrix operations.