A trichotomy for regular simple path queries on graphs - Archive ouverte HAL Access content directly
Journal Articles Journal of Computer and System Sciences Year : 2020

A trichotomy for regular simple path queries on graphs

(1) , (2, 3) , (4)
1
2
3
4

Abstract

We focus on the computational complexity of regular simple path queries (RSPQs). We consider the following problem RSPQ(L) for a regular language L: given an edge-labeled digraph Gand two nodes xand y, is there a simple path from x to y that forms a word belonging to L? We fully characterize the frontier between tractability and intractability for RSPQ(L). More precisely, we prove RSPQ(L)is either AC0, NL-complete or NP-complete depending on the language L. We also provide a simple characterization of the tractable fragment in terms of regular expressions. Finally, we also discuss the complexity of deciding whether a language L belongs to the fragment above. We consider several alternative representations of L: DFAs, NFAs or regular expressions, and prove that this problem is NL-complete for the first representation and PSpace-complete for the other two.
Fichier principal
Vignette du fichier
jcss19 (1).pdf (659.61 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02435355 , version 1 (25-09-2020)

Identifiers

Cite

Guillaume Bagan, Angela Bonifati, Benoit Groz. A trichotomy for regular simple path queries on graphs. Journal of Computer and System Sciences, 2020, 108, pp.29-48. ⟨10.1016/j.jcss.2019.08.006⟩. ⟨hal-02435355⟩
105 View
269 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More