Path Querying with Conjunctive Grammars by Matrix Multiplication
- Autores: Azimov R.1,2, Grigorev S.1,2
-
Afiliações:
- St. Petersburg State University
- JetBrains Research
- Edição: Volume 45, Nº 7 (2019)
- Páginas: 357-364
- Seção: Article
- URL: https://journals.rcsi.science/0361-7688/article/view/176926
- DOI: https://doi.org/10.1134/S0361768819070041
- ID: 176926
Citar
Resumo
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.
Palavras-chave
Sobre autores
R. Azimov
St. Petersburg State University; JetBrains Research
Autor responsável pela correspondência
Email: st013567@student.spbu.ru
Rússia, St. Petersburg, 199034; St. Petersburg, 197374
S. Grigorev
St. Petersburg State University; JetBrains Research
Autor responsável pela correspondência
Email: s.v.grigoriev@spbu.ru
Rússia, St. Petersburg, 199034; St. Petersburg, 197374