A trichotomy for regular simple path queries on graphs

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 G and two nodes x and y, is there a simple path from x to y that forms a word belonging to L? We fully characterize the f...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2020-03, Vol.108, p.29-48
Main Authors: Bagan, Guillaume, Bonifati, Angela, Groz, Benoit
Format: Article
Language:English
Subjects:
Automata
Complexity
Computer Science
Graphs
Paths
Regular languages
Regular simple paths
Web
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 G and two nodes x and 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 ▪, ▪-complete or ▪-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 ▪-complete for the first representation and ▪-complete for the other two.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2019.08.006