24 citations · 40 across the 6 of their papers we have counts for
6 papers
GLL-based Context-Free Path Querying for Neo4j
Vadim Abzalov, Vlada Pogozhelskaya, Vladimir Kutuev +1
We propose GLL-based context-free path querying algorithm which handles queries in Extended Backus-Naur Form (EBNF) using Recursive State Machines (RSM). Utilization of EBNF allows…
Fine-grained reductions around CFL-reachability
Aleksandra Istomina, Semyon Grigorev, Ekaterina Shemetova
In this paper we study the fine-grained complexity of the CFL reachability problem. We first present one of the existing algorithms for the problem and an overview of conditional l…
One Algorithm to Evaluate Them All: Unified Linear Algebra Based Approach to Evaluate Both Regular and Context-Free Path Queries
Ekaterina Shemetova, Rustam Azimov, Egor Orachev +2
The Kronecker product-based algorithm for context-free path querying (CFPQ) was proposed by Orachev et al. (2020). We reduce this algorithm to operations over Boolean matrices and…
Rational index of bounded-oscillation languages
Ekaterina Shemetova, Alexander Okhotin, Semyon Grigorev
The rational index of a context-free language is a function , such that for each regular language recognized by an automaton with states, the intersection of …
Context-Free Path Querying by Matrix Multiplication
Rustam Azimov, Semyon Grigorev
Graph data models are widely used in many areas, for example, bioinformatics, graph databases. In these areas, it is often required to process queries for large graphs. Some of the…
Context-Free Path Querying with Structural Representation of Result
Semyon Grigorev, Anastasiya Ragozina
Graph data model and graph databases are very popular in various areas such as bioinformatics, semantic web, and social networks. One specific problem in the area is a path queryin…