EFFICIENT PREPROCESSING OF SIMPLE BINARY PATTERN FORESTS

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.