Containment of Nested Regular Expressions
classification
💻 cs.DB
keywords
regularcontainmentexpressionsbeennestednresproblemanalysis
read the original abstract
Nested regular expressions (NREs) have been proposed as a powerful formalism for querying RDFS graphs, but research in a more general graph database context has been scarce, and static analysis results are currently lacking. In this paper we investigate the problem of containment of NREs, and show that it can be solved in PSPACE, i.e., the same complexity as the problem of containment of regular expressions or regular path queries (RPQs).
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
The Equational Theory of Relational Kleene Algebra with Graph Loop is PSPACE-Complete
Relational Kleene algebra with graph loop has a PSPACE-complete equational theory over relational models.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.