Containment of Nested Regular Expressions

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 t...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-06
Main Author: Reutter, Juan L
Format: Article
Language:English
Subjects:
Containment
Software reviews
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:2331-8422