2 papers
cs.DB2021
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…
cs.FL2020
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 …