Skip to Main content Skip to Navigation
Journal articles

A trichotomy for regular simple path queries on graphs

Guillaume Bagan 1 Angela Bonifati 2, 3, 4, 1 Benoit Groz 5
3 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
4 BD - Base de Données
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/hal-02435355
Contributor : Tyrex Equipe <>
Submitted on : Friday, September 25, 2020 - 11:49:08 AM
Last modification on : Saturday, January 9, 2021 - 3:40:29 AM
Long-term archiving on: : Thursday, December 3, 2020 - 5:43:14 PM

File

jcss19 (1).pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

116

Files downloads

124