Adaptive Pattern Matching.
Pattern 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  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.
Introduction
Pattern matching is a fundamental operation in a number of important applications such as functional
and equational programming, term rewriting and theorem proving. In most of these applica-
tions, patterns are partially ordered by assigning priorities. For instance, in languages such as ML
[5] and Haskell [6], a pattern occurring earlier in the text has a higher priority over those following
it. Applications that do not impose priorities can also be handled as a special case of matching
with priorities.
The typical approach to pattern matching is to preprocess the patterns into a DFA-like automaton
that can rapidly select the patterns that match the input term 1 . The main advantage of
such a matching automaton is that all pattern matches can be identified in a single scan (i.e., no
backtracking) of portions of input term relevant for matching purposes and is done in time that
is independent of the number of patterns. Fig. 1 shows such a matching automaton constructed
on the basis of a left-to-right traversal of patterns. This automaton can be represented by tables
or compiled into case statements. Each state of the automaton corresponds to the prefix of the
input term seen in reaching that state and is annotated with the set of patterns that can possibly
match. For instance, state s 4 corresponds to having inspected the prefix f(b; a; x), where x denotes
the subterm that has not yet been examined. This state is annotated with the pattern set f1; 2; 3g
since we cannot rule out a match for any of the three patterns on the basis of the prefix f(b; a; x).
Research partially supported by NSF grants CCR-8805734,9102159,9110055 and NYS S&T grant RDG 90173.
y This research was completed at SUNY, Stony Brook.
Only matches at the root of the input term are identified. Nonlinearity is not considered since even in applications
that allow such patterns, most failures are associated with symbol mismatches, as observed in [3].
\Gamma\Psi @ @R
\Gamma\Psi
\Gamma\Psi @ @R
f2g f1g f3g f1g
f
a
a
a
\Gamma\Psi @ @R
@ @R
\Gamma\Psi f3g


Figure

1: Left-to-right (left) and adaptive automata (right) for f(x; a; b); f(b; a; a); f(x; a; y) with
textual order priority. Here x and y denote variables.
Pattern matching automata have been extensively studied for well over a decade. Augustsson [1]
and Wadler [14] describe pattern matching techniques based on left-to-right traversal. A drawback
with these methods is that they may reexamine symbols potentially several times; so in the worst
case they may end up testing each pattern separately against the input term. This drawback is
overcome by the methods of Christian, Graf and Schnoebelen, which are again based on left-to-right
traversals or variants thereof. However, their space requirements can become exponential in the
size of patterns.
One way to improve space and matching time is to engineer a traversal order to suit the set of
patterns or the application domain. We refer to such traversals as adaptive traversals and automata
based on such traversals as adaptive automata. As traversal orders are no longer fixed apriori, an
adaptive automaton must specify the traversal order. For instance, in the adaptive automaton
shown in fig. 1, each state is labelled with the next argument position to be inspected from that
state. Adaptive traversal has two main advantages over a fixed-order of traversal such as left-to-
right.
ffl The resulting automaton can be smaller, e.g., the adaptive automaton in fig. 1 has 8 states
compared to 11 in the left-to-right automaton. The reduction factor can even become exponential.
ffl Pattern matching requires lesser time with adaptive traversals than fixed-order traversals.
Furthermore, fixed-order traversals cannot use the priority information to avoid inspection of symbols
irrelevant for determining highest priority matches. For instance, the adaptive automaton
announces a match for pattern 1 after examining only the last two arguments of f whereas the
left-to-right automaton needs to inspect all three arguments. Observe that examining unnecessary
runs counter to the goals of lazy evaluation in the context of functional programs.
The design of adaptive automata is the focus of this paper. In the process, we study several
important problems that have remained open even in the context of automata based on fixed-order
traversals. These problems include lower and upper bounds on space complexity, construction of
optimal dag automata and the impact of typing in pattern matching.
1.1 Summary of Results
We first formalize the concept of adaptive traversal and its special case, namely, fixed traversal
orders and then present an algorithm for constructing adaptive automata.
ffl In section 3 we examine space and matching time complexity. We show that the space
requirements of the automata can be quite large by establishing the first known tight exponential
lower bounds on size. These results are quite difficult to obtain since proofs must be independent
of traversal order.
ffl In section 4 we present several techniques to synthesize traversal orders that can improve space
and matching time. We first develop the important concept of a representative set which forms the
basis of several optimization techniques aimed at avoiding inspection of unnecessary symbols. We
present a quadratic-time algorithm for computing representative sets in untyped systems whereas
we show that computing these sets is NP -complete for typed systems.
ffl We then present several powerful strategies for synthesizing traversal orders. Through an
intricate example, we show that they all can sometimes increase both space and matching time.
We therefore present another strategy based on selecting indices that overcomes this drawback.
Huet and Levy [7] had established the importance of index in the design of optimal automata for
strongly-sequential patterns. Our results extend the applicability of indices even for patterns that
are not strongly-sequential.
ffl In section 4 we synthesize a traversal S(T ) from a given traversal T (such as left-to-right)
by inspecting index positions whenever possible. Using S(T ) in place of T does not affect the
termination properties of a functional program. So the programmer can continue to assume T
whereas an implementation can benefit from significant improvements in space and time using
ffl In section 5 we describe an orthogonal approach to space minimization based on dag represen-
tation. By tightly characterizing equivalence of states we directly build an optimal dag automaton.
This important problem had remained open [4] even for left-to-right traversals.
ffl In section 6 we focus on the important problem of index computation in prioritized systems.
Laville [9], Puel and Suarez [11] have extended Huet-Levy's [7] index computation algorithm to
deal with priorities. However, these algorithms require exponential time in the worst case. In
contrast, we present the first polynomial-time algorithm for index computation in untyped systems.
Furthermore, we also show that this problem is co-NP -complete for typed systems. We therefore
present powerful heuristics that can significantly speed up this process in typed systems.
ffl Our work clearly brings forth the impact of typing in pattern matching. We have shown
that several important problems in the context of pattern matching are unlikely to have efficient
algorithms in typed systems whereas we have given polynomial time algorithms for them in untyped
systems. This clearly demonstrates that typing makes algorithms inherently more complex rather
than serve as an optimization that aids in pruning the search space for index computation, as
suggested in [9]. Finally, implications of our results are discussed in section 7. Some proof details
are omitted in the main paper, but can be found in the appendix.
Preliminaries
In this section we introduce notations that will be used in the rest of this paper. We also present a
generic algorithm for adaptive automata construction that forms the basis for the results presented
in later sections.
We assume familiarity with the basic concept of a term. We use root(t) to denote the symbol
appearing at the root of a term t. The notion of a position is used to refer to subterms in a term
as follows. A position is either the empty string   that reaches the root or p:i (p is a position and
i an integer) which reaches the ith argument of the root of the subterm reached by p. We use t=p
to refer to the subterm of t reached by p and t[p / s] to denote the term obtained by replacing the
subterm t=p by s. A substitution maps variables to terms. An instance tfi of a term t is obtained
by substituting fi(x) for every variable x in t. If t is an instance of u then we say u call u
a prefix of t. Fringe of u is the set of all variable positions in u. We will use x; y and z to denote
variables, ' ' to denote any unnamed variable and a; b; c; d; f to denote nonvariables. We say that
two terms t and s unify iff they possess a common instance. t t s denotes the least such instance
in the ordering given by -.
A top-down traversal inspects nodes in a term successively and is characterized by a selection
function that, having inspected a prefix u, chooses the next position to visit. The match set L u of
a prefix u is the set of patterns that unify with u. Let P denote the set of fringe positions of u
wherein at least one pattern in L u has a nonvariable.
Adaptive and Fixed Traversals: An adaptive traversal is a top-down traversal wherein the
position next visited is a function of the prefix u and the given set of patterns L. In a fixed
traversal order p is simply a function of P .
Pattern We say that a pattern l 2 L matches t iff t - l and t 6- l 0 for any l 0 with priority
higher than that of l. If there is any such l in L then we say there is a pattern match for t. Among
patterns of equal priority, we may announce a match for a term t if it is an instance of any one of
these patterns.
Ambiguous and Unambiguous Systems: A set of patterns L is said to be ambiguous whenever
there is more than one pattern that can match any given term. Otherwise L is unambiguous.
Typed Systems: In typed systems, the set of allowable input terms are constrained by a type
discipline. For instance, this constraint may take the form that arguments to a function f must be
drawn from the set fT ; Fg. In this case, terms f(T are allowable
Untyped Systems: In untyped systems, there is no such type discipline. Hence the allowable
input terms include any term over any alphabet \Sigma 0 that is a superset of the alphabet \Sigma used in the
patterns.
which there is a pattern match, t=p is a nonvariable. Intuitively, index is a position that must be
examined to determine a pattern match, e.g., any fringe position of u where every pattern in L u
has a nonvariable is an index.
2.1 Generic Algorithm to build Adaptive Automata
A state v of the automaton remembers the prefix u inspected in reaching v from the start state.
Suppose that p is the next position inspected from v. From v there are transitions on all symbols
c that are present at p for any l 2 L u . There will also be a transition from v on 6= which will be
taken on seeing a symbol different from those on the other edges. A generic algorithm to construct
an adaptive automaton is given below. Observe that priorities are implicitly handled by definition
of match.
Procedure Build(v; u)
1. Let M denote patterns that match u.
2. If M 6= OE then matchset[v] := M. /  State v announces a match for patterns in M
3. else
4. select is a function to choose the next position to inspect  /
5. position to inspect is recorded in the pos field  /
6. for each symbol for which 9l 2 L u with nonvariable c) do
7. create a new node v c and an edge from v to v c labelled c
8.
9. If 9l 2 L u with a variable at p or at an ancestor of p then
10. create a new node v 6= and an edge from v to v 6= labelled 6=
11. Build(v
Build is similar to previously known algorithms such as that of Christian [3] and Huet-Levy
[7]. The main difference is that Build is generic whereas the others prespecified the select function.
Build is invoked by the call Build(s is the start state of the automaton. It takes two
parameters - v specifies a state of the automaton and u specifies the prefix examined in reaching
jm
@
@R
J-
\Omega \Omega AE
\Gamma\Psi
\Phi-
1:2c
d
s
s
s
c 2,4
2:2
cb
1,2,4 2:3
2:1
a

l 3
l 1
e
e
e
@
@
@
@I
l 4
l 3
l 2
l 1

Figure

2: Adaptive automaton constructed by Build for patterns shown at top-right, with priorities
as in bottom-right. The pos field and L u are shown with each state. States labelled s denote
identical subtrees.
state v. This invocation of Build constructs the subautomaton rooted at v. Lines 6, 7 and 8 create
transitions based on each symbol that could appear at p for any pattern in L u . In line 8, Build is
recursively invoked with the prefix extended to include the symbols seen on the transitions created
in line 7. If there is a pattern in L u with a variable at or above p then a transition on 6= is created
at line 10 and Build recursively invoked at line 11. Fig. 2 shows a set of patterns along with their
priorities and the corresponding automaton constructed by Build. The automaton has 25 states
since states labelled s all have identical subtrees each with 4 states.
Observe that there can be at most S positions of interest (recall that S is the sum of the sizes
of all the patterns). Each position, which is an integer sequence, can be encoded as an integer. We
omit the details of such an encoding which can be found in implementations such as equals [10].
Using such an encoding, the symbol specified by any position can be accessed without any extra
overhead when compared to fixed-traversal orders. Finally, observe that the automata generated
by Build has a tree structure which is also the representation used by all previous pattern matching
methods. Popularity of trees stems from their simplicity and the fact that they readily support
case statement representation.
3 Space and Matching Time Complexity
We now examine upper and lower bounds (independent of traversal order) on the space and matching
time complexity of adaptive tree automata for several classes of patterns. Fig. 3 summarizes
our results. Observe that the contribution by depth of the automata (whose upper bound is S)
to space is insignificant compared to the exponential lower bound. The major contribution comes
from the breadth of the automata. Furthermore, even for patterns without variables (i.e. ground
terms) it is hard to reduce the number of states [2] whereas reducing breadth is not. Therefore in
the rest of the paper, we will use breadth as the measure of size of the automaton.
We now present the details of lower bound proofs. The proofs for upper bounds can be established
along the lines of [4, 12]. The space bounds given in this section are all independent of the
2 The size of a pattern is the number of nonvariable symbols in it.
Class of Patterns Lower bound Upper bound Lower bound Upper bound
on space on space on time on time
Unambiguous, no priority
Unambiguous, with priority \Omega\Gamma a n ) O(
Ambiguous

Figure

3: Space and matching time complexity of adaptive automata. Here n; S; a and jl i j denote
respectively the number of patterns, sum of their sizes 2 , average size and the size of ith pattern.6 6 6 4
a a a a
b a a
b b a

Figure

4: Example Matrix for
a a a
b b a
a a
b b a

Figure

5: Matrices representing L u for states
reached by transitions on a and b.
traversal order and are established using flat patterns that all have a root symbol f with arbitrarily
large arity. It can be shown that for purposes of buiding either the smallest size automaton or one
that does matching in the shortest possible time, flat patterns are equivalent to a set of patterns
having a common prefix u whose fringe size equals arity of f . (This is because every symbol in
the common prefix will have to be inspected on any path to any final state. Then it follows by
theorem 4 (section 4.3) that the automaton that inspects all these symbols first is no larger than
any other automaton.)
3.1 Unambiguous, Unprioritized Patterns
Consider a set of n nonoverlapping patterns from the alphabet ff; a; bg and variables. Since all flat
patterns have the same root symbol f , we need only specify the arguments. Therefore n patterns
can be represented by a matrix of n rows, where the ith row lists the arguments of f in the ith
pattern. Each column has at most one occurrence of a, at most one occurrence of b and the rest are
all ' 's. For each pair of patterns l and l 0 , there is at least one column wherein l and l 0 have different
nonvariables and so the system is unambiguous. Fig. 4 shows such a matrix that represents the
four patterns f(a; a;
the size of the smallest automaton with n such patterns. Now pick any position (i.e., column)
to discriminate. If this column contains only one nonvariable then on a positive transition (i.e.,
transition on a or b) we will once again be left with the same L u without any reduction in the
problem size. For instance, in fig. 4 if we choose column 7 for inspection then we are left with the
problem of building an automaton to match on the basis of the first six positions of each pattern.
In other words, we are left with a matrix obtained from that of fig 4 by deleting the last column
and hence the problem is still an instance of S(4). On the other hand if the column contains two
nonvariables then based on the symbol seen in the column we can now partition the n patterns
into two sets each consisting of patterns. These sets must be further discriminated and hence
we have two instances of S(n \Gamma 1), e.g., in the above example, inspecting position 2 results in the
pattern sets f1; 2; 4g and f2; 3; 4g as shown in fig. 5. Hence:
whose solution is
3.2 Unambiguous Prioritized Patterns
To derive lower bound on the size of the automaton for unambiguous prioritized set of patterns,
consider the following set of flat patterns with textual order priority:
Using the set of patterns constructed as above, we obtain a lower bound on space of \Omega\Gamma a n ) as
follows. Denote by S(n) the size of the automaton for patterns of the above form. It can be shown
that the smallest size automaton is obtained by first inspecting all the c's and then the a in the
first column, then those in the second column and so on. (This because it can be shown that
each position examined in automaton thus obtained is an index. Then it follows by lemma 4 (see
section 4.3) that this automaton is no larger than any other automaton.) Now consider the first
m states of the automaton. Each state has a 6= branch that leads to a subautomaton for matching
patterns. Therefore:
whose solution is m n . Noting that m is the average size of patterns, we have the lower bound a n .
3.3 Ambiguous Patterns
Consider again the set of patterns used in section 3.2. Now assume that there is no priority among
these patterns. Observe that the automata A for this set of patterns (which must report all matches
since there is no priority relationship among the patterns) can be used as an automaton for the
prioritized system considered in the previous section. To do this, on reaching a final state v, we
simply announce a match for the pattern with the highest priority among those in matchset[v].
Hence this automaton cannot be any smaller than that for patterns with priority. Thus we arrive
at a lower bound of \Omega\Gamma a n ) for ambiguous unprioritized patterns. The same lower bound holds even
when priorities are allowed since the automata for unprioritized patterns can be used for matching
prioritized patterns in the manner mentioned above.
3.4 Matching Time
One possible measure of matching time is the average root-to-leaf path length of the automaton.
This measure can exhibit the following anomaly. Suppose an automaton A has the property that
for each path in automaton A 0 , the corresponding path(s) in A is shorter or has the same length.
Then clearly A has better matching time but this may not be reflected in the average root-to-leaf
path lengths. The reason for this is that there may be several paths in A 0 that correspond to a
single path in A. Suppose that there is one path P of length 2 in A and another path Q of length 7.
Also assume that there are two paths in A 0 corresponding to P with length 3 and one corresponding
to Q with length 7. Note that although each path in A is shorter than (or equal in length to) the
corresponding path in A 0 , the average path length of A is 4:5 whereas the average path length of
A 0 is only 4:3!
A good measure that does not suffer from such an anomaly is average over the mean matching
times for all patterns, where the mean matching time for a pattern l is the average path length
of those paths that lead to a matching state for l. This quantity is 4:5 for A whereas it is 5 for
A 0 . Based on this measure, upper and lower bounds on matching time are given in fig. 3. These
bounds are established with the same construction used to obtain the space bounds.
Synthesizing Traversal Orders
Observe that Build does not specify the selection function. We now present several techniques that
can be used in any combination to derive selection functions for improving space and matching
time.
4.1 Representative Sets
Suppose v is the state reached on seeing prefix u. Observe that there may be patterns in L u for
which no match is announced at any descendant of v. For instance, consider the patterns in fig. 2
and the prefix Although L observe that a match for l 4 can be
declared only if the 3rd argument of f is b. In such a case we declare a match for the higher
priority pattern l 1 . Inspecting any position only on behalf of a pattern such as l 4 is wasteful, e.g.,
inspection of position 1 for u is useless since it is irrelevant for declaring a match for l 1 . To avoid
inspecting such positions, we identify a representative set L u that is a minimal set consisting only
of those patterns for which a match is announced at a descendant of v. In the above example
g. Representative sets form the core of several optimizations discussed later. Laville's
notion of accessible patterns [9] is the same as our representative set. Our contribution here is
that our definition yields a simple algorithm for computing this set. The definition of accessible
patterns does not yield such an algorithm and so [9] uses the notion of compatible patterns (which
corresponds to our match set L u ) in place of accessible patterns. Observe that we can also use
L u in place of L u in all the following optimizations, but doing so may make the optimizations less
effective. For instance, our algorithm for directly building optimal dag automata (see section 5)
will fail to identify some equivalent states if L u is used in place of L u .
To compute L u note that any pattern l that has the following property need not be present in
a match for l is identified for a term t at a descendant of v we can also identify a
match for another pattern (of equal or higher priority) for the same term. A precise definition of
the property is
We can arrive at L u by repeatedly deleting patterns such as l. However, the above definition does
not immediately lend itself to a decision procedure since it refers to an infinite number of instances
of u. Although the set of terms t to be considered can be restricted to a finite set, it still does not
lead to an efficient procedure since:
Theorem 1 Computing L u is NP -complete for typed systems.
The proof of this therem uses a reduction similar to that used in the proof of theorem 9 (see
section 6.2). We omit the proof details here. For untyped systems a more efficient method can be
developed by considering only l t u and not its instances. Specifically,
Theorem 2 L u can be computed in O(nS) time in untyped systems by deleting l such that
Proof: First we need to show that the two characterizations of the l to be deleted are equivalent.
It is easy to see that any l satisfying the second characterization will also satisfy the first one. To
show that any l that satisfies the first characterization also satisfies the second, let l 1 ; :::; l k be all
those patterns such that any instance v of l and u (and hence of l t u) is also an instance of one
of l 1 ; :::; l k . Now consider the term t obtained from l t u by instantiating each variable by 6=. This
term cannot be an instance of some l i unless l i - (l t u). Observe that this l i can serve the role of
l 0 in the second characterization. Thus the two characterizations are equivalent. It can be easily
seen that computing L u using the simpler characterization can be done in O(nS) time.
Note that in the above definition, if l and l 0 have equal priority and l t
one can be retained in L u and the other discarded. (This choice will not affect the structure of the
automaton below the current state, but will only determine whether a match is announced for l or
l 0 in a final state below.) Except for the choice among such patterns, the second definition specifies
L u uniquely. Finally, note that in unambiguous systems L
4.2 Greedy Strategies
We resort to greedy strategies for implementing function select since dynamic programming approach
will take exponential time as the subautomata themselves can have exponential size. We
begin by listing several strategies to choose a p such that:
1. the number of distinct nonvariables at p in any pattern in L u is minimized.
2. the number of distinct nonvariables at p in any pattern in L u is maximized.
3. the number of patterns having nonvariables at p is maximized.
4. Let L 1 ; :::; L r be the match sets of the children of v. Then max(jL 1 j; :::; jL r j) is minimized.
5. \Sigma r
For improving space, the rationale for these strategies is as follows. Strategy 1 locally minimizes
the breadth. Strategy 2 attempts to distinguish quickly among patterns so as to contain the
(potentially exponential) blow-up. Since only patterns with a variable at p are duplicated among
the children of v, strategy 3 minimizes their number. Strategy 5 carries this one step further
by minimizing the number of such duplications. Strategy 4 attempts to minimize the size of the
largest subautomaton rooted at any child of v since it determines the size of the automaton in case
of blow-up's. For improving time, strategy 3 (and also 5) minimizes the number of patterns for
which inspection of the symbol at p is unnecessary. For strategies 2 and 4 observe that in the worst
case, time spent in matching below v is proportional to sum of sizes of patterns in L u . By quickly
discriminating among patterns, this quantity can be rapidly reduced.
All of the above greedy strategies suffer from the drawback that:
Theorem 3 For each of the above greedy strategies there exist pattern sets for which automata of
smaller size and matching time can be obtained by making a choice different from that given by the
greedy strategy.
Proof: For strategies 2,3,4 and 5 consider the following set of patterns with equal priorities:
After inspecting the root, all these strategies will choose one of positions 2,3 or 4. It can be shown
(by enumerating all possible matching automata for these patterns) that the smallest breadth,
number of states and matching time obtainable by this choice are 20, 47 and 4.25 respectively.
These figures can be reduced to 15, 45 and 4 respectively by choosing position 1.
The construction of this example is quite intricate. The key idea is to make each of the pattern
sets f1; 4; 5; 6g; f2; 4; 5; 6g and f3; 4; 5; 6g strongly-sequential 3 whereas any set containing two of the
first three patterns and one of the last three is not.
3 In strongly-sequential systems, any prefix u with must have an index.
4.3 Selecting Indices
We now propose an important strategy that does not suffer the drawbacks of the above strategies.
The key idea is to select a p that is an index for u. We show that this strategy yields automaton of
smaller (or same) size and smaller (or same) matching time than obtainable by any other choice.
The importance of index was known only in the context of strongly-sequential systems. Our result
demonstrates its applicability to patterns that are not strongly-sequential. Specifically, given a
subautomata A rooted at v that selects some position p, we construct another subautomata A 0
that selects an index q and show that size and matching time of A 0 are no greater than that of
A. This construction proceeds through a series of steps each of which interchange the order of
positions q and another position seen immediately preceding it. The following theorem (stated
without proof) makes the above construction precise.
Theorem 4 With p; q and v as above suppose that pos(w) = q for every child w of v. Then the
order of inspection of p and q can be interchanged without increasing the size or matching time of
the automaton. By repeating this interchange we can obtain A 0 from A.
It is quite interesting to note that repetition of interchange steps which is permitted only under
restrictive conditions, is sufficient to globally rearrange the traversal order in A to get A 0 . Although
the theorem only asserts that size and matching time of A 0 is no larger than that of A, fig. 6 shows
that they can be strictly smaller for A 0 . We remark that by doing interchange steps as above, size
can sometimes be reduced byas much as an exponential factor and time by O(n).
Using arbitrary traversal orders (determined at compile time) is not appropriate in functional
programming since termination properties of the program depend on the traversal order. Therefore
the programmer must be made aware of the traversal order apriori. Given this constraint, we now
show that it is possible to internally change the traversal order in such a way that it does not affect
the termination properties and at the same time realize the advantages of adaptive traversal 4 .
Given a prefix u, suppose a traversal order T selects p
as the next position to be visited. T is said to be monotonic iff for any prefix u
variable), the traversal once again selects p unless u 0 =p corresponds to a variable position 8l 2 L u 0 .
Traversals that possess monotonicity property include most known traversal orders such as
depth-first and breadth-first (as well as variations of these without left-to-right bias). In particular
it includes all fixed-traversal orders mentioned earlier such as left-to-right and right-to-left. It also
includes traversals used in implementations of strongly-sequential systems.
Given a monotonic traversal T , we can obtain another traversal S(T ) from it by inspecting
indices whenever possible without affecting termination properties. Specifically, let S(T ) denote
the traversal that uses the following strategy to pick the position to inspect for a prefix u.
ffl If u has indices then arbitrarily select one of them.
ffl Otherwise, select the position in the fringe of u that will be the first to be visited by T .
Theorem 6 Size and matching time can never become worse if S(T ) is used in place of T . Each
path in the automaton using S(T ) examines a subset of the positions examined on the corresponding
path in T .
Minimizing Space using DAGs
The previous section discussed synthesizing traversal orders in order to improve space and time.
We now discuss an orthogonal approach to minimize space based on sharing equivalent states. An
4 We remark that this transformation is applicable only to functional languages with no side-effects.
-:
-:
\Omega \Omega \Omega OE
a
a
a
@ @R
-:
f
a
a

Figure

Example to illustrate size and matching time reduction due to transformation. Figure
shows automata for f( ; b); f(a; a) and f( ; a) with textual order priority.
obvious way to achieve sharing is to use standard FSA minimization techniques for optimizing
the tree automaton constructed by Build. A more efficient method is to identify equivalence of
two states without even generating the subautomata rooted at these states. Observe that the tree
automaton may be exponentially larger than the dag automaton, in which case the naive approach
uses exponential time and space whereas direct construction can potentially use only polynomial
space and polynomial time. This important problem of directly building an optimal automata even
when restricted to left-to-right traversals has remained open [4]. We now propose a solution to this
problem.
To identify equivalent states, suppose that two prefixes u 1 and u 2 have the same representative
set L u and differ in positions p such that every pattern in L u has a variable at or above p. Since
such positions are irrelevant for determining a match, these two prefixes are equivalent. On the
other hand, it can also be shown that if they have different representative sets or differ in any other
position then they are not equivalent. Based on this observation, we define the relevant prefix
of u as the term obtained by replacing subterms at positions such as p above by the symbol 6=.
For instance, the prefixes corresponding to different states marked 's' in fig. 2 are different, but
they all have the same relevant prefix f(x; 6=; b). By showing that two states are equivalent iff the
corresponding relevant prefixes are identical we
Theorem 7 The automaton obtained by merging states with identical relevant prefixes is optimal.
Merging equivalent states as described above can substantially reduce the space required by the
automata, e.g., the tree automaton in fig. 2 has 25 states which can now be reduced to 16 by
sharing. Also recall that for the patterns in fig. 4, parts of the automaton reached by positive
transitions alone is exponential. We can show that by sharing states this part of the automaton
will become polynomial!
5.1 Impact of DAGs on Space and Matching Time Complexity
Since sharing affects space requirements alone, all the results established so far not relating to
space (such as theorem 6 for time) continue to hold for dags as well. In what follows we discuss
the impact of dags on some of the results established earlier regarding space. We can show that
the upper bound on size of dag automata is O(2 n S) which is much smaller than the corresponding
bound O(
automata. We can also establish a lower bound of O(2 n ) for ambiguous
patterns. For unambiguous patterns, it is not clear whether the lower bound on size is exponential.
For instance, it appears that the patterns used in the lower bound proof on size of tree automata for
unambiguous patterns, possess a polynomial-size dag automaton. Reasoning about lower bounds
becomes extremely complicated for dags since it is difficult to capture behavior of sharing formally.
Finally, all the greedy strategies as well as the strategy of selecting indices can, in some cases,
increase the space of dag automata. The failure of the index selection strategy further demonstrates
the complexity of sharing.
Recall that an index for a prefix u is a position on its fringe that must be inspected to announce
a match for any pattern in L u . In the absence of priorities, the positions that must be inspected
to announce a match for a pattern l are exactly those fringe positions wherein l has a nonvariable.
With priorities, however, we may have to inspect positions wherein l has a variable in order to rule
out a match for higher priority patterns. But it is not obvious which variable position of l must be
inspected and so it is not clear how to compute indices in prioritized systems. Therefore Laville [8]
proposed an indirect method for index computation that first transforms the prioritized patterns
into an equivalent set of unprioritized patterns, which is then used for index computation. For
each pattern l, the transformation generates a set M l of its instances that are not instances of any
higher priority pattern. (For typed systems, only those instances that observe the type discipline
are generated.) The transformed system is S
l2L M l .
Puel and Suarez [11] developed a compact representation for the sets M l based on the notion
of constrained terms. These are terms with constraints placed on the substitutions taken by the
variables in them. For instance, the constrained term feq(x; y)j(x 6= a) - (y 6= b)g denotes the set
of terms
A precise semantics of constrained terms is given by first regarding a term t with variables as
denoting the set I(t) of its instances. Now the constrained term ftj'g denotes the set of instances
of t that also satisfy the constraint formula '. To define a constraint formula, first define an atomic
constraint to be of the form t 6= s or of the form x 6= s, where x is a variable in t and all the
variables in s are unnamed 5 . In the former case the terms that satisfy the constraint must belong
to the set I(t) \Gamma I(s). In the latter case, the substitution taken by x must not be an instance of s.
An arbitrary constraint is obtained by combining atomic constraints using - and -. A constraint
'-/ is satisfied by all (and only) terms that satisfy either ' or /. Similarly, the constraint '- /
is satisfied by all (and only) terms that satisfy ' as well as /. Finally, note that in typed systems,
there is always an implicit constraint imposed by the type discipline that requires a variable to be
substituted only by a term that is of the same type as the variable. Henceforth we may use several
methods to simplify constrained terms. These methods are quite intuitive and their correctness
readily follows from the above semantics.
Using constrained terms the set M l can be represented compactly as
flj(l
are all the patterns with priority greater than l. The constraints l 6= l i can be
simplified to constraints on the variables in l. To simplify a constraint l 6= l 0 , we first check if the
two patterns unify. If not, the constraint simplifies to true. Otherwise, let x be all the
variables in l that are substituted by nonvariable terms (say unifying l and l 0 . Then
the simplified constraint is
Using this procedure, simplification of all the constraints on a pattern l can be done in O(S) time.
For illustration, consider the following example that defines equality on an enumerated data type
5 This is to prevent having constraints such as x 6= a(y) - y 6= b that will complicate the development of the
materials in the rest of the section.
Note that no two among the first n patterns unify and so the condition
vacuously and hence the first n patterns appear unchanged in the transformed system. The last
rule, however, unifies with every other rule and gets translated into
where the condition in the ith disjunct prevents instances of the ith pattern from being recognized
as instances of the last rule.
As seen above, the constraints are in CNF and it is not clear how indices can be obtained from
them. So Puel and Suarez simplify it into DNF which makes the structure of the terms in the set
denoted by a constrained term apparent. For instance, when the above constrained term
simplifies to:
Note that in typed systems, constraints such as x 6= a 1 - x 6= a 2 will be simplified to false and so
the above constraint simplifies to [x 6= a 1 - y 6= a 2
Once a constrained term t is in DNF, indices of a prefix u w.r.t. t c can be
easily picked as follows. Firstly, any variable position of u wherein t has a nonvariable symbol is an
index for u. Secondly, consider any variable position p wherein t has a variable x, but a constraint
on the substitution for x appears in every conjunct ' i . Note that for any term to be an instance
of this constrained term, it must satisfy one of the constraints ' 1 through 'm . Since x appears in
every one of these conjuncts, its substitution must be examined in order to determine whether a
term satisfies the constraint. Therefore all such positions are also indices of u.
The above conversion of the constraint on a pattern l from CNF to DNF is very expensive and
can take O(jlj n ) time. Therefore Puel and Suarez's algorithm, which is based on such a conversion,
has exponential time complexity for both typed and untyped systems. Laville's algorithm is also
exponential for typed and untyped systems. In contrast, we now present the first polynomial-time
algorithm for untyped systems that operates directly on the original patterns.
6.1 Algorithm for Index Computation in Untyped Systems
The index for a prefix is computed in two steps. First we compute the set of indices of the prefix
w.r.t. each of the constrained patterns in L u . The intersection of the sets thus computed yields the
indices of the prefix w.r.t. L u . We compute the indices of a prefix u w.r.t. to a single constrained
pattern l as follows:
be the patterns in L u that have priority over l and also unify with l. Following
two steps specify the indices of u w.r.t. l.
1. Each variable x in u such that l has a nonvariable at the position corresponding to x.
2. Each variable x that must be the only position to be instantiated in l tu to determine a match
for some higher priority pattern l j .
We remark that a similar algorithm was suggested by Laville as a heuristic for fast index
computation. However, the question of the power (or completeness) of the heuristic is not addressed
at all. We now illustrate the algorithm on l (with
textual order priority) and the prefix z). Observe that x; y and z are all indices of l 1
by step 1. The only index for l 2 is x by step 1. Observe that step 2 does not yield any additional
indices for l 2 . For l 3 , z is an index by step 1 and x is an index by step 2 (with l
intersection of all these positions is x which is therefore an index for u. Index computation takes
time using this algorithm. We show:
Theorem 8 The algorithm for computing indices in untyped systems is sound and complete.
Proof: We need only establish that the above algorithm computes all and only the indices of u
w.r.t. the constrained pattern
l
Clearly, any position computed using step 1 is an index w.r.t. l c . For any position selected using
step 2 observe that the constraint l 6= l j will simplify to x 6= t for some term t; so the constraint
will appear in every conjunct in the DNF of fl. All the positions selected in step 2 are thus
indices of l c .
For completeness, we need to show that if a position p in u is not selected by steps 1 or 2 then
it is not an index of l c . This is accomplished by giving an instance of l c that has a variable at
p. Suppose that p is not selected by step 1 or step 2. Then for each l i , it must be the case that
either l i =p is a variable or that there is more than one position in the fringe of l t u that need to
be instantiated for determining a match for l i . In either case, the disjunct obtained by simplifying
l 6= l i contains at least one literal different from l=p. Consider the
s obtained from l t u by substituting 6= for each of the x i 's mentioned above. Note that the
substitutions for the variables in l t u satisfies the constraints in l c . Hence s is an instance of l and
but still has a variable at p. This proves that p is not an index of u.
For typed systems it is very unlikely we can escape exponential complexity since we show:
For intuition into the reason for the complexity gap between typed and untyped systems, we draw
an analogy between index computation with constrained terms and the satisfiability problem. Note
that the literals in constraints generated by Puel and Suarez's algorithm are all of the form x 6= t
where x is a variable and t an arbitrary term. Such constrained terms are analogous to boolean
formulas with only negative literals. Such boolean formulas are trivially satisfiable (by a truth
assignment that assigns false to every literal). Similarly index computation is simple in untyped
systems. However, in typed systems, there are implicit positive constraints introduced by the type
discipline. For instance, there is an implicit constraint on the constrained
term (1). Thus we have a constraint that contains both positive and negative literals. Such a
constrained term is analogous to a boolean formula with both positive and negative literals and
hence the complexity gap.
Proof: The index selection problem, when posed as a decision problem, takes the form "Does u
possess an index w.r.t. pattern set L?" To show that this problem is in co-NP , we need to show
that the problem of deciding whether p is not an index is in NP . To do this, let r be the
set of fringe nodes of u. We first guess r instances of u such that t i =p i is a variable for
r. Then we verify that each t i is an instance of (at least) one of the patterns in L and if
so we declare that u has no index. All this can clearly be accomplished in polynomial time and
hence the problem of determining whether u does not possess an index is in NP and so the index
selection problem is in co-NP .
To show that the problem is co-NP -complete, we reduce the complement of satisfiability to
this problem. Let ' be an instance of satisfiability problem where ' i is a disjunct
of literals of the form x or :x, x 2 fx g. We transform this into an index computation
problem in the following system consisting of n+ 1 patterns, with textual order priority. The roots
of these patterns is the symbol f (which once again stands for the common prefix shared by all
the patterns) with arguments. The last m arguments of f are of a type that consists of
nonvariables a and b. The (n 1)th pattern is of the form f(x To specify the first n
be terms that do not unify with each other. Also assume that there is a term
t of the same type as which does not unify with any of these terms. Now we specify the
ith pattern (for 1 is a or b depending upon whether x j or :x j
occurs in ' i . If neither occur in ' i then s j is a variable. Observe that the size of this pattern set
is polynomial in the size of ' . With this construction, we will now show that determining
whether an index is equivalent to determining whether
First we transform the above pattern set into a set of constrained patterns. Following the
transformation the (n + 1)th pattern becomes
Here we have slightly abused the notation in replacing x j 6= a by x j and x j 6= b (i.e. x j 6= a by
type discipline) by :x j . By using heuristic 1, this constraint can be simplified to
which shows that f(x 0 ; :::; xm ) has an index (namely x 0 ) iff the input to the SAT problem
is not satisfiable.
6.3 Heuristics for Fast Index Computation in Typed System
Suppose the constrained term is of the form
are disjuncts that do not contain occurrences of x. Suppose
that there exists a term t (valid for type of x) such that t does not equal any of t
Then:
Rule 1: The indices obtainable from the above constraint are exactly those obtainable from the
constrained term
are the only terms valid for type of x then:
Rule 2: If each ' i consists only of a single variable y, then y is an index.
The power of rule 1 is evident from the fact that in order to apply it we need only identify some
variable x such that the constraints on x do not simplify to false 6 . Once such an x is identified, we
can avoid expanding fl into 2 n terms and instead concern ourselves with just two of the terms in
the expansion, namely,
To illustrate the power of rule 2 consider the constrained term in (1). Note that x 6= a 1 - x 6=
a simplifies to false and the ' i 's (which are of the form y 6= a i ) also contain only
6 By saying "' reduces to false'' we mean that ' is not satisfiable, i.e., it is a contradiction.
one variable y and hence y is an index. Interchanging the role of x and y we also note that x is an
index. Note that computing these indices has taken time linear in sum of sizes of rules. In contrast,
Puel and Suarez's algorithm spends exponential time reducing the constraint to DNF.
Proof of Correctness of Rule 1: Expanding fl and taking the conjunction with ffi we get
where ffl is a disjunction of terms containing at least one constraint on x and some "s. The first
term in this expansion constrains only x. Therefore no variable other than x that appears in any
' i can be an index unless it appears in every conjunct in DNF of ffi. Furthermore, since x apears
in all the terms in the above expansion except fl 0 , it is clear that x will be an index iff fl 0 reduces
to false. This is exactly captured by considering only [(x
Proof of Rule 2: Once again we expand fl as above and eliminate the term
which reduces to false. Now observe that every other conjunct in the expansion contains at least
one ' i . If each ' i is of the form y 6= t i then each conjunct in DNF will constrain y and so y is an
index.
7 Concluding Remarks
In this paper we studied pattern matching with adaptive automata. We presented lower and upper
bounds on the worst-case size of the automata for several classes of patterns. We then discussed
how to improve space and matching time by synthesizing traversal orders. We showed that a good
traversal order selects indices whenever possible and uses one of the greedy strategies (especially
strategy 4 or 5) otherwise. Although the greedy strategies may sometimes fail, it appears from the
complexity of the counter examples that such failures may be rare. For functional programming,
we synthesized a traversal S(T ) from a monotonic traversal T . Since using S(T ) does not affect
termination properties, the programmer can assume T whereas an implementation can benefit from
significant improvements in space and matching time.
We also discussed an orthogonal approach to space minimization by sharing equivalent states.
Recall that even the index selection strategy may fail to improve space of dag automata. This
occurs because index selection may adversely affect the way in which descendants of a state can be
shared. Since it is difficult to predict sharing among descendant states, the possibility of improving
space without using indices does not appear to be practical. So the best approach is to use all
the strategies in section 4 and use sharing as an additional source of space optimization over tree
automata.
Our work clearly brings forth the impact of typing in prioritized pattern matching. We have
shown that several important problems in the context of pattern matching are unlikely to have
polynomial-time algorithms for typed systems whereas we have given polynomial-time algorithms
for them in untyped systems. This raises the question whether it is worthwhile to consider typing
for pattern matching. It is not clear how often typing information can be used to find an index
(or to determine that a pattern does not belong to L u ) which cannot be found otherwise. On the
other hand there is a significant penalty in terms of computational effort for both these problems
if we use typing information.



--R


Complexity of Trie Index Construction


The Definition of Standard ML
Report on Haskell
Computations in Nonambiguous Linear Term Rewriting Systems
Lazy Pattern Matching in the ML Language
Implementation of Lazy Pattern Matching Algorithms
Fast Parallel Implementation of Functional Languages - The EQUALS Experience

Refined Compilation of Pattern Matching for Functional Languages
TR 14/91
Efficient Compilation of Pattern Matching
--TR

--CTR
Nadia Nedjah, Minimal deterministic left-to-right pattern-matching automata, ACM SIGPLAN Notices, v.33 n.1, January 1998
Nadia Nedjah , Luiza de Macedo Mourelle, Efficient concise deterministic pattern-matching automata for ambiguous patterns, ACM SIGPLAN Notices, v.37 n.2, February 2002
Per Gustafsson , Konstantinos Sagonas, Efficient manipulation of binary data using pattern matching, Journal of Functional Programming, v.16 n.1, p.35-74, January 2006
R. Sekar , I. V. Ramakrishnan , Andrei Voronkov, Term indexing, Handbook of automated reasoning, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 2001
indexing;discrimination nets;functional programming;algorithms and complexity;pattern matching