Relational Kleene algebra with graph loop has a PSPACE-complete equational theory over relational models.
Containment of Nested Regular Expressions
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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).
fields
cs.LO 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
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.