Search

• < Previous
• 1
• Next >

---

Fine-Grained Complexity of Regular Path Queries

Katrin Casel ; Markus L. Schmid.

A regular path query (RPQ) is a regular expression q that returns all node pairs (u, v) from a graph database that are connected by an arbitrary path labelled with a word from L(q). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between&nbsp;[&hellip;]

---

Refl-Spanners: A Purely Regular Approach to Non-Regular Core Spanners

Markus L. Schmid ; Nicole Schweikardt.

The regular spanners (characterised by vset-automata) are closed under the algebraic operations of union, join and projection, and have desirable algorithmic properties. The core spanners (introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, JACM 2015) as a formalisation of the core&nbsp;[&hellip;]

---