Tree Pattern Matching to Subset Matching in Linear Time

Tree Pattern Matching to Subset Matching in Linear Time
复制标题

DOI：
10.1137/s0097539700382704
复制
发表时间：
2003
期刊：
SIAM J. Comput.
影响因子：
--
通讯作者：
R. Cole;R. Hariharan
R. Cole;R. Hariharan
中科院分区：
其他
文献类型：
--
作者：
R. Cole;R. Hariharan

文献摘要

被引文献

相似文献

在本文中，我们显示了从树模式匹配问题到另一个称为子集匹配问题的问题的O（n+M）时间变化。随后的作品为子集匹配问题提供了有效的确定性和随机算法。这些作品共同产生O（NLOG2M +M）时间确定性算法和O（N log N +M）时间蒙特卡洛算法，用于树模式匹配问题。
In this paper, we show an O(n+m) time Turing reduction from the tree pattern matching problem to another problem called the subset matching problem. Subsequent works have given efficient deterministic and randomized algorithms for the subset matching problem. Together, these works yield an O(nlog2m +m) time deterministic algorithm and an O(n log n+m) time Monte Carlo algorithm for the tree pattern matching problem.