Regular matching and inclusion on compressed tree patterns with constrained context variables
Information and Computation(2022)
摘要
We study the complexity of regular matching and inclusion for compressed tree patterns with context variables subject to regular constraints. Context variables with regular constraints permit to properly generalize on unranked tree patterns with hedge variables. Regular inclusion on unranked tree patterns is relevant to certain query answering on Xml streams with references. We show that regular matching and inclusion with regular constraints can be reduced in polynomial time to the corresponding problem without regular constraints.
更多查看译文
关键词
Tree patterns,Tree automata,Computational complexity,Streams,Xml,Grammar compression
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要