Path Querying with Conjunctive Grammars by Matrix Multiplication

Результат исследований: Научные публикации в периодических изданияхстатья


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.

Язык оригиналаанглийский
Страницы (с-по)357-364
Число страниц8
ЖурналProgramming and Computer Software
Номер выпуска7
СостояниеОпубликовано - 1 дек 2019

Предметные области Scopus

  • Программный продукт

Fingerprint Подробные сведения о темах исследования «Path Querying with Conjunctive Grammars by Matrix Multiplication». Вместе они формируют уникальный семантический отпечаток (fingerprint).