Multipattern matching in trees is fundamental to a variety of programm
ing language systems. A bottleneck in this connection has been the com
binatorial problem of constructing the immediate subsumption tree for
a simple binary pattern forest. We reduce the complexity of this probl
em from O(n(2)) time and O(n(2)) space to O(n log n) time and O(n) spa
ce. 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). (C) 1996 Academi
c Press. Inc.