Path Querying with Conjunctive Grammars by Matrix Multiplication
- Authors: Azimov R.1,2, Grigorev S.1,2
-
Affiliations:
- St. Petersburg State University
- JetBrains Research
- Issue: Vol 45, No 7 (2019)
- Pages: 357-364
- Section: Article
- URL: https://journals.rcsi.science/0361-7688/article/view/176926
- DOI: https://doi.org/10.1134/S0361768819070041
- ID: 176926
Cite item
Abstract
Problems in many areas can be reduced to one of the formal-languages-constrained path problems. Conjunctive grammars are more expressive than context-free grammars and are used, for example, in static analysis to describe an interleaved matched-parentheses language, which is not context-free. 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 (General-Purpose computing on Graphics Processing Units) computing techniques and other optimizations for matrix operations.
About the authors
R. Azimov
St. Petersburg State University; JetBrains Research
Author for correspondence.
Email: st013567@student.spbu.ru
Russian Federation, St. Petersburg, 199034; St. Petersburg, 197374
S. Grigorev
St. Petersburg State University; JetBrains Research
Author for correspondence.
Email: s.v.grigoriev@spbu.ru
Russian Federation, St. Petersburg, 199034; St. Petersburg, 197374