ADAPTIVE PATTERN-MATCHING

Pattern matching is an important operation used in many applications s uch as functional programming, rewriting, and rule-based expert system s. By preprocessing the patterns into a deterministic finite state aut omaton, we can rapidly select the matching pattern(s) in a single scan of the relevant portions of the input term. This automaton is typical ly based on left-to-right traversal of the patterns. By adapting the t raversal order to suit the set of input patterns, it is possible to co nsiderably reduce the space and matching time requirements of the auto maton. The design of such adaptive automata is the focus of this paper . We first formalize the notion of an adaptive traversal. We then pres ent several strategies for synthesizing adaptive traversal orders aime d at reducing space and matching time complexity. In the worst case, h owever, the space requirements can be exponential in the size of the p atterns. We show this by establishing an exponential lower bound on sp ace that is independent of the traversal order used. We then discuss a n orthogonal approach to space minimization based on direct constructi on of optimal directed acyclic graph (dag) automata. Finally, our work stresses the impact of typing in pattern matching. In particular, we show that several important problems (e.g., lazy pattern matching in M L) are computationally difficult in the presence of type disciplines, whereas they can be served efficiently in the untyped setting.