English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Regular path queries (RPQs) select nodes connected by some path in a graph.The edge labels of such a path have to form a word that matches a given regularexpression. We investigate the evaluation of RPQs with an additional constraintthat prevents multiple traversals of the same nodes. Those regular simple pathqueries (RSPQs) find several applications in practice, yet they quickly becomeintractable, even for basic languages such as (aa)* or a*ba*.  In this paper, we establish a comprehensive classification of regularlanguages with respect to the complexity of the corresponding regular simplepath query problem. More precisely, we identify the fragment that is maximal inthe following sense: regular simple path queries can be evaluated in polynomialtime for every regular language L that belongs to this fragment and evaluationis NP-complete for languages outside this fragment. We thus fully characterizethe frontier between tractability and intractability for RSPQs, and we refineour results to show the following trichotomy: Evaluations of RSPQs is eitherAC0, NL-complete or NP-complete in data complexity, depending on the regularlanguage L. The fragment identified also admits a simple characterization interms of regular expressions.  Finally, we also discuss the complexity of the following decision problem:decide, given a language L, whether finding a regular simple path for L istractable. We consider several alternative representations of L: DFAs, NFAs orregular expressions, and prove that this problem is NL-complete for the firstrepresentation and PSPACE-complete for the other two. As a conclusion we extendour results from edge-labeled graphs to vertex-labeled graphs and vertex-edgelabeled graphs.

A Trichotomy for Regular Simple Path Queries on Graphs