On Injective Embeddings of Tree Patterns

Details On Injective Embeddings of Tree Patterns On Injective Embeddings of Tree Patterns

2012-04-22

arxiv.org/abs/1204.4948v1

Computer Science

Databases

Under conference submission

Scientific paper

We study three different kinds of embeddings of tree patterns: weakly-injective, ancestor-preserving, and lca-preserving. While each of them is often referred to as injective embedding, they form a proper hierarchy and their computational properties vary (from P to NP-complete). We present a thorough study of the complexity of the model checking problem i.e., is there an embedding of a given tree pattern in a given tree, and we investigate the impact of various restrictions imposed on the tree pattern: bound on the degree of a node, bound on the height, and type of allowed labels and edges.

Affiliated with

Also associated with

No associations

Rating

On Injective Embeddings of Tree Patterns does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Injective Embeddings of Tree Patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Injective Embeddings of Tree Patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-443321