Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables

摘要

We study the complexity of regular matching and inclusion for compressed tree patterns extended by context variables. The addition of context variables to tree patterns permits us to properly capture compressed string patterns but also compressed patterns for unranked trees with tree and hedge variables. Regular inclusion for the latter is relevant to certain query answering on X_(ML) streams with references.