Path Querying with Conjunctive Grammars by Matrix Multiplication

Standard

Path Querying with Conjunctive Grammars by Matrix Multiplication. / Azimov, R.; Grigorev, S.

In: Programming and Computer Software, Vol. 45, No. 7, 01.12.2019, p. 357-364.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{fd13b3d3f5a64342a0fcdbeb8995202b,

title = "Path Querying with Conjunctive Grammars by Matrix Multiplication",

abstract = "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.",

keywords = "conjunctive grammars, GPGPU, graphs, matrix multiplication, path querying, static analysis, transitive closure",

author = "R. Azimov and S. Grigorev",

year = "2019",

month = dec,

day = "1",

doi = "10.1134/S0361768819070041",

language = "English",

volume = "45",

pages = "357--364",

journal = "Programming and Computer Software",

issn = "0361-7688",

publisher = "МАИК {"}Наука/Интерпериодика{"}",

number = "7",

}

RIS

TY - JOUR

T1 - Path Querying with Conjunctive Grammars by Matrix Multiplication

AU - Azimov, R.

AU - Grigorev, S.

PY - 2019/12/1

Y1 - 2019/12/1

N2 - 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.

AB - 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.

KW - conjunctive grammars

KW - GPGPU

KW - graphs

KW - matrix multiplication

KW - path querying

KW - static analysis

KW - transitive closure

UR - http://www.scopus.com/inward/record.url?scp=85076473892&partnerID=8YFLogxK

U2 - 10.1134/S0361768819070041

DO - 10.1134/S0361768819070041

M3 - Article

AN - SCOPUS:85076473892

VL - 45

SP - 357

EP - 364

JO - Programming and Computer Software

JF - Programming and Computer Software

SN - 0361-7688

IS - 7

ER -

ID: 50702212