Matching Subsequences in Trees
<|reference_start|>Matching Subsequences in Trees: Given two rooted, labeled trees $P$ and $T$ the tree path subsequence problem is to determine which paths in $P$ are subsequences of which paths in $T$. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.<|reference_end|>
@article{bille2005matching,
    title={Matching Subsequences in Trees},
    author={Philip Bille and Inge Li Goertz},
    journal={arXiv preprint arXiv:cs/0512061},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0512061},
    primaryClass={cs.DS}
}