|
|
Adaptive Pattern MatchingPattern matching is an important operation used in many applications such as functional
programming, rewriting and rule-based expert systems. By preprocessing the patterns into a
DFA-like automaton, we can rapidly select the matching pattern(s) in a single scan of the
relevant portions of the input term. This automaton is typically based on left-to-right
traversal of the patterns. By adapting the traversal order to suit the set of
input patterns, it is possible to considerably reduce the space and matching time
requirements of the automaton. The design of such adaptive automata is the focus of this
paper. We first formalize the notion of an adaptive traversal. We then present several
strategies for synthesizing adaptive traversal orders aimed at reducing space and matching
time complexity. In the worst case, however, the space requirements can be exponential in
the size of the patterns. We show this by establishing the first known an exponential
lower bounds on space that is independent of the traversal order used. We then
discuss an orthogonal approach to space minimization based on direct construction
of optimal dag automata. Finally, our work brings forth the impact of typing in pattern
matching. In particular, we show that several important problems (e.g., lazy pattern
matching in ML) are computationally hard in the presence of type disciplines, whereas they
can be solved efficiently in the untyped setting. |
|
Maintained by Sekar, sekar@cs.sunysb.edu |