Tree Pattern Matching to Subset Matching in Linear Time
Richard Cole, Ramesh Hariharan · SIAM Journal on Computing · 2003
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(nlog 2 m +m) time deterministic algorithm and an O(n log n+m) time Monte Carlo algorithm for the tree pattern matching problem.