ADAPTIVE PATTERN-MATCHING

Citation
Rc. Sekar et al., ADAPTIVE PATTERN-MATCHING, SIAM journal on computing, 24(6), 1995, pp. 1207-1234
Citations number
26
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
ISSN journal
0097-5397
Volume
24
Issue
6
Year of publication
1995
Pages
1207 - 1234
Database
ISI
SICI code
0097-5397(1995)24:6<1207:AP>2.0.ZU;2-Y
Abstract
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.