Efficient Preprocessing of Simple Binary Pattern Forests

Multipattern matching in trees is fundamental to a variety of programming language systems. A bottleneck in this connection has been the combinatorial problem of constructing the immediate subsumption tree for a simple binary pattern forest. We reduce the complexity of this problem fromO(n²) time andO(n²) space toO(n log n) time andO(n) space. Such a result was conjectured possible in 1982 by C. Hoffmann and J. O'Donnell (J. Assoc. Comput. Mach.29(1) (1982), 68–95) and in 1992 finding it was called a main open problem by J. Cai, R. Paige, and R. Tarjan (J. Theoret. Comput. Sci.106(1992), 21–60).