Optimal Left-to-Right Pattern-Matching Automata
Nadia Nedjah*, Colin D. Walter and Stephen E. Eldridge
Computation Dept., UMIST, PO. Box 88, Manchester M60 1QD, UK.
nn, cdw, see @sna.co.umist.ac.uk

www.co.umist.ac.uk

Abstract
We propose a practical technique to compile pattern-matching for prioritised
overlapping patterns in equational languages into a minimal, deterministic, left-toright, matching automaton. First, we present a method for constructing a tree
matching automaton for such patterns. This allows pattern-matching to be
performed without any backtracking. Space requirements are reduced by using a
directed acyclic graph (dag) automaton that shares all the isomorphic subautomata
which are duplicated in the tree automaton. We design an efficient method to
identify such subautomata and avoid duplicating their construction while generating
the dag automaton. We conclude with some easily computed bounds on the size ofthe automata, thereby improving on previously known equivalent bounds for the tree
automaton.
Keywords: Term rewriting system, pattern-matching, tree automaton, dag automaton.

1. Introduction
The key technical problems in implementing equational computations as reduction
sequences are finding redexes, choosing which redex to reduce at each step andperforming the reduction. The first stage is often called pattern-matching and this canbe achieved as in lexical analysis by using a finite automaton. In order to avoid
backtracking over symbols already read, extra patterns are added. These correspond tooverlaps in the prefixes of original patterns. In this paper, we focus on avoiding the
duplication of subautomata caused by the repetition of pattern suffixes when these newpatterns are added. This results in a more efficient pattern-matcher. Consequently wealso obtain much improved bounds on the size of the recognising automaton.
A simple-minded way of pattern-matching is to try each rule sequentially until aleft-hand side is matched or the whole pattern set is exhausted. However, this method
may consume considerable effort unnecessarily. Usually, patterns are pre-processed to
produce an intermediate representation allowing the matching to be performed more
efficiently. One such representation consists of a matching automaton [3, 4, 7].
Here we concentrate on another method of building minimal (with respect to size),deterministic (i.e. no backtracking), matching automata for prioritised, overlapping
patterns. First, a method for generating a deterministic tree matching automaton for agiven pattern set is described. Although the generated automaton is efficient since it
avoids symbol re-examination, it can only achieve this at the cost of increased space.
As we shall see, the main reason for the increase in space requirements is the
duplication of functionally identical or isomorphic subautomata in the tree-based
automaton. However, the problem of directly constructing matching automata that do
not duplicate such subautomata has not been previously described [2, 11]. We tackle*

Author sponsored by the British Council and the Algerian Ministry for High Education.

274

Lecture Notes in Computer Science, vol. 1298, pp. 273-286, Springer, 1997.

this next, describing a method that efficiently identifies equivalent states that would
lead to identical subautomata and then constructing the equivalent reduced dag-based
automaton. This is achieved without explicitly constructing the tree automaton first.
Finally, we bound the size of the dag automaton using easily obtained parameters.

2. Notation and Definitions
In this section, we recall the notation and concepts that will be used in the rest of thepaper. Symbols in a term are either function or variable symbols. The non-empty set
of function symbols F = {a, b, f, g, ...} is ranked i.e., every function symbol f in F has
an arity which is the number of its arguments and is denoted #f. A term is either aconstant, a variable or has the form ft1 t2...t#f where each ti, 1 ≤ i ≤ #f, is itself a term.
We abbreviate terms by removing the usual parenthesis and commas. This isunambiguous in our examples since the function arities will be kept unchanged
throughout, namely #f = 4, #g = #h = 2, #a = #b = 0. Variable occurrences are
replaced by ω, a meta-symbol which is used since the actual symbols are irrelevant
here. A term containing no variables is said to be a ground term. We generally
assume that patterns are linear terms, i.e. each variable symbol can occur at most oncein them. Pattern sets will be denoted by L and patterns by π1, π2, ..., or simply by π.
A term t is said to be an instance of a pattern π if there exists a substitution σ for thevariables of π such that t = σπ.
Definition 2.1: A position in a term is a path specification which identifies a node in
the parse tree of the term. Position is specified here using a list of positive integers.
The empty list Λ denotes the position of the root of the parse tree and the position p.k(k≥1) denotes the root of the kth argument of the function symbol at position p.
Positions of symbols in a term can be totally ordered according to the left-to-rightorder of the symbols in the term or the pre-order traversal of the parse tree. Thisordering generalises to cases where the positions are of symbols in different terms
because we can compare their integer lists lexicographically. So any set of positions
can be put in left-to-right order.
Definition 2.2: A matching item is a triple r:α•β where αβ is a term and r is a rulelabel. The label identifies the origin of the term αβ and hence, in a term rewriting
system, the rewrite rule which has to be applied when αβ is matched. The label is not
written explicitly below except where necessary. The meta-symbol • is called thematching dot, α and β are called the prefix and suffix respectively, and the first symbolof β is called the matching symbol. The position of the matching dot is called thematching position and is identified with the position of the matching symbol. A final
matching item is one of the form α•. It has a final matching position which we writeas ∞.
Throughout this paper left-to-right traversal order is used. So the matching item •βrepresents the initial state prior to matching the pattern β. In general, the matchingitem α•β denotes that the symbols in α have been matched and those in β have not yet
been recognised. Finally, the matching item α• is reached on successfully matching
the whole pattern α.
Definition 2.3: A set of matching items in which all the items have the same prefix iscalled a matching set. A matching set in which all the items have an empty prefix iscalled an initial matching set whereas a matching set in which all the items have anNedjah, Walter & Eldridge, Optimal Pattern-Matching Automata

275

empty suffix is called a final matching set. The rule set for a matching set is the set oflabels appearing in its items.
Definition 2.4: For a set L of pattern suffixes and any symbol s, let L\s denote the setof pattern suffixes obtained by removing the initial symbol s from those members of L
which commence with s. Then, for f ∈ F define Lω and Lf by:
Lω
Lf

L\ω

=
=

{

L \ f ∪ ω #f L \ ω if L \ f = ∅∅otherwise

where ω#f denotes a string of #f symbols ω. The closure L of a pattern set L is thendefined recursively by Gräf [2] as follows:
if L = {ε} or L = ∅

L

L

=

{U

s∈F ∪{ω } s Ls

otherwise

Roughly speaking, with two item suffixes of the form fα and ωβ we always add thesuffix fω#fβ in order to postpone by one more symbol the decision between these twopatterns. Otherwise backtracking might be required to match ωβ if input f leads tofailure to match fα.

3. Tree Matching Automata
In this section, we describe a practical and efficient method to construct a tree
matching automaton for a prioritised overlapping pattern set. The pattern set L isconverted into the above closed pattern set L while generating the matching
automaton. In general, the construction technique described here is inspired by the
LALR method used in YACC to generate parsers for LR-languages [1,5]. This has
been used for many years to compile imperative languages. The pattern set to becompiled is considered as a set of right-hand sides of syntactic productions. However,there are no Shift-Reduce or Reduce-Reduce conflicts since we are only treating root
matching of the input and the priority rule enables us to resolve multiple matches.
The pattern set compiles into a deterministic tree matching automaton which isrepresented by the 4-tuple 〈S0, S, S∞ , δ〉 where S is the state set, S0 ∈ S is the initialstate, S∞ ⊆ S is the final state set and δ is the state transition function. The states arelabelled by matching sets which consist of original patterns whose prefixes match thecurrent input prefix, together with extra instances of the patterns which are added to
avoid backtracking in reading the input. In particular, the matching set for S0 contains
the initial matching items formed from the original patterns and labelled by the rules
associated with them. Transitions are considered according to the symbol at thematching position, i.e. that immediately after the matching dot. For each symbol s ∈F∪{ω} and state with matching set M, a new state with matching set δ(M,s) is derived
using the composition of the functions accept and close defined in Figure 3.1.

276

Lecture Notes in Computer Science, vol. 1298, pp. 273-286, Springer, 1997.

accept(M,s) = {r:αs•β  r:α•sβ ∈ M }close(M)= M ∪ {r:α•fω#fµ  r:α•ωµ ∈ M and∃ q:α•fλ ∈M for some suffix λ and f∈F }δ(M,s)= close( accept(M,s) )Figure 3.1: Automata Transition Function
The items obtained by recognising the symbols in those patterns of M where s is thenext symbol form the set accept(M,s) which is called the kernel of δ(M,s). However,the set δ(M,s) may contain more items. The presence of two items α•ωµ and α•fλ in M
creates a non-deterministic situation since the variable ω could be matched by a term
having f as head symbol. The item α•fω#fµ is added to remove this non-determinism
and avoid backtracking. The transition function thus implements simply the main stepin the closure operation described by Gräf [2] and set out in the previous section.
Hence the pattern set resulting from the automaton construction using the transition
function of Figure 3.1 coincides with the closure operation of Definition 2.4. The item
labels simply keep account of the originating pattern for when a successful match isachieved.
Non-determinism is worst where the input can end up matching the whole of two
different patterns. Then we need a priority rule to determine which pattern to select.
Definition 3.2: A pattern set L is overlapping if there is a ground term that is an
instance of at least two distinct patterns in L. Otherwise, L is non-overlapping.
Definition 3.3: A priority rule is a partial ordering on patterns such that if π1 and π2
are overlapping patterns then either π1 has higher priority than π2 or π2 has higher
priority than π1.
When a final state is reached, if several rules have been successfully matched, thenthe priority rule is engaged to select the one of highest priority. Examples of priority
rules are the textual and specificity priority rules. The textual rule is used in the
majority of functional languages. Among the matched patterns, the rule chooses thepattern that appears first in the text. The specificity rule [6] can be used only if for any
pair of overlapping patterns, one pattern is an instance of the other. The former patternis said to be more defined than the latter. So among the matched patterns, the rulechooses the most defined pattern. Whatever rule is used, we will apply the word match
only to the pattern of highest priority which is matched.
Definition 3.4: A term t matches a pattern π ∈ L if, and only if, t is an instance of π
and t is not an instance of any other pattern in L of higher priority than π.
Example 3.5: Let L = {faaωa, fgaωaab, fωbbb} be the set of patterns of rules
numbered 1, 2 and 3 respectively. The matching automaton for L is given in Figure
3.6. Each state is labelled with its matching set. Transitions corresponding to failures
are omitted, and an ω-transition is only taken when there is no other available
transition which accepts the current symbol. The automaton can be used to drive thepattern-matching process irrespective of the chosen term rewriting strategy.

277

Nedjah, Walter & Eldridge, Optimal Pattern-Matching Automata

0
1 • faaωa2 • fgaωaab
3 • fωbbbf
1
1 f • aaωω
2 f • gaωaab
3 f • ωbbb
3 f • abbb
3 f • gωωbbb

3
a

1 fa • aωa
3 fa • bbbab8
1 faa • ωa
ω
11
1 faaω • aa
14
1 faaωa •9(3)3 fab • bb

4(1)3 fω • bbb

ω

b
9(1)
3 fωb • bb

g
2

b

12(3)
3 fabb • b
b

b
12(1)
3 fωbb • b

2 fg • aωaab
3 fg • ωωbbb
3 fg • aωbbb

b15(1)3 fωbbb •15(3)ω

3 fabbb •5a6
2 fga • ωaab
3 fga • ωbbb

3 fgω • ωbbb

ω4(2)3 fgωω • bbb

ω7
2 fgaω • aab
3 fgaω • bbb

b9(2)3 fgωωb • bbb10
2 fgaωa • abba
13
2 fgaωaa • b12(2)3 fgωωbb • b
15(2)

a

3 fgωωbbb •b16
2 fgaωaab •b9(4)3 fgaωb • bbb12(4)3 fgaωbb • b
b15(4)3 fgaωbbb •Figure 3.6: Tree Automaton for {1: faaωa, 2: fgaωaab, 3: fωbbb}

4. Optimal Pattern-Matching Automata
The tree automaton described above is time efficient during operation because it avoids
symbol re-examination. However, it achieves this at the cost of increased spacerequirements. The unexpanded automaton corresponding to the pattern set of Figure
3.6, and to which no patterns are added, is given in Figure 4.1. It is much smaller.
There, fabbb is only recognised by backtracking from state 2 to state 1 and then taking
the branch through state 4 instead. But in Figure 3.6 a branch recognising fabbb has
been added to avoid backtracking, thereby duplicating the existing sub-branch which

278

Lecture Notes in Computer Science, vol. 1298, pp. 273-286, Springer, 1997.

recognises the bbb in fωbbb. We can see similar duplication in several other branchesof Figure 3.6; those identified by sharing the same main state numbers.
By sharing duplicated branches, the tree automaton can be converted into an
equivalent but smaller directed acyclic graph (dag) automaton. States which recognise
the same inputs and assign the same rule numbers to them are functionally equivalent,and can be identified. For instance, the dag automaton corresponding to Figure 3.6 isgiven in Figure 4.2. The number of states is thereby reduced from 27 to 17, leaving
just one state more than in the non-deterministic machine of Figure 4.1.
a

2

5

ω

1

a

8

11

a
f

0

g

1

a

3

6

ω

9

a

a

12

ω

2

b

14

15

3
4

7

b

b

10

13

b

Figure 4.1: Unexpanded Automaton for { 1: faaωa,2: fgaωaab,3: fωbbb}
0

1 • faaωa2 • fgaωaab
3 • fωbbb
f
1
1 • aaωa2 • gaωaab
3 • ωbbb
3 • abbb
3 • gωωbbba

ω

22 • aωaab
3 • ωωbbb
3 • aωbbbgω
53 • ωbbb

ω
4

3
1 • aωa3 • bbb1 • ωaω8b
93 • bb11b12

2 • ωaab
3 • ωbbbω7

3 • bbbbaa
62 • aab3 • bbbba

10

2 • ab
a

13

1 •a

3•b

2 •b

a

b

b

1

14

15

3

16

2

Figure 4.2: Dag Automaton for {1: faaωa, 2: fgaωaab, 3: fωbbb}

Nedjah, Walter & Eldridge, Optimal Pattern-Matching Automata

279

By sharing duplicated branches, the tree automaton can be converted into an
equivalent but smaller directed acyclic graph (dag) automaton. States which recognise
the same inputs and assign the same rule numbers to them are functionally equivalent,and can be identified. For instance, the dag automaton corresponding to Figure 3.6 isgiven in Figure 4.2. The number of states is thereby reduced from 27 to 17, leaving
just one state more than in the non-deterministic machine of Figure 4.1.
The above example hides the complexity of recognising duplication where a numberof suffixes are being recognised, not just one. The required dag automaton can begenerated using finite state automaton minimisation techniques but this may require a
lot of memory and time. The obvious alternative approach consists of using thematching sets to check new states for equality with existing ones while generating theautomaton. In the case of equality, the new state is discarded and the existing one isshared. However, comparison of matching sets may be prohibitively expensive and it
may well require bookkeeping for all previously generated matching sets. A major aimof this paper is to show how to avoid much of this work. First we must characterise
states that would generate isomorphic subautomata.
Definition 4.3: Two matching items r1:α1•β1 and r2:α2•β2 are equivalent if, and only
if, the suffixes and rule labels are equal, i.e. β1 = β2 and r1 = r2. Otherwise, they are
inequivalent.
Definition 4.4: Two matching sets M1 and M2 are equivalent if, and only if, to every
item i in M1 ∪ M2 there correspond items i1 ∈ M1 and i2 ∈ M2 which are equivalent toi. Otherwise, the sets are inequivalent.
For instance, in Figure 3.6 the matching sets labelling the states 9(1) and 9(2) areequivalent whereas the matching sets labelling the states 3 and 4(2) are inequivalent.
Clearly, equivalence is the right criterion for coalescing nodes of the tree automaton to
obtain the equivalent dag automaton: such sets will certainly accept the same pattern
suffixes and result in the same rewrite rule being applied. So,
Lemma 4.5: Two matching sets generate identical automata if they are equivalent.
We believe this equivalence is actually necessary as well as sufficient to combine
corresponding states in the automaton. However, equivalent matching sets may havedifferent prefixes, as can be seen in Figure 3.6. Since only the suffixes are relevant tomatching, only they appear labelling the states in Figure 4.2.

5. Dag Matching Automaton Construction
In this section, we describe how to build the minimised dag automaton efficiently
without first constructing the tree automaton. This requires the construction of a list ofmatching sets in a suitable order to ensure that every possible state is obtained, and ameans of identifying potentially equivalent states.
The items in matching sets all share a common prefix before the matching dot (e.g.
see Figure 3.6), namely the string of symbols recognised before reaching the matchingposition. Hence, the matching position of any item is an invariant of the wholematching set. The states of the tree automaton can therefore be ordered using the leftto-right total ordering on the common matching positions of their matching sets.
Unfortunately, states which are functionally equivalent may not share the same
matching position (see [8]). So the matching position is not uniquely defined for a

280

Lecture Notes in Computer Science, vol. 1298, pp. 273-286, Springer, 1997.

state in the dag automaton. However, one way of assigning an acceptable and uniquematching position to a dag state is always to choose the leftmost (or the rightmost)position of all the states which have been coalesced. This is done starting with theinitial state and working downwards.
The dag automaton is constructed as in Algorithm 5.1. We iteratively construct themachine using a list l of matching sets in which the sets are ordered according to thematching position of the set. So the initial matching set is first and final matching sets
come last. Each set in l is paired with its corresponding state in the automaton and apointer is kept to the current position in the list l.
Algorithm 5.1: Initialise l to contain just the pair of the initial matching set and state,and set the current pointer to it. For the iterative step, let 〈M,S〉 be the current pair in l.
For each symbol s ∈ F∪{ω}, compute the non-empty matching sets δ(M,s) as defined
above. If there is no pair 〈M',S'〉 in l such that δ(M,s) is equivalent to M' then create astate S', add it to the automaton with a transition labelled s from S to S' and insert thepair 〈δ(M,s),S'〉 into l according to the matching position of δ(M,s). Otherwise, i.e.
when such a pair 〈M',S'〉 already exists in l, create a transition s from S to S'. Lastly,
increment the pointer to the next matching set in l, if such exists, and repeat. The
process halts when the end of the list l is reached.
The list l represents the equivalence classes of matching states where the assigned
matching position is that of the representative which is generated first. In each new set
which is generated, the position of the current matching set is incremented at least one
place to the right. So new members of l are always inserted to the right of the current
position. This ensures that all necessary transitions will eventually be generated
without moving the pointer backwards in l. It is easy to see from the definition of theclose function that added patterns cannot contain positions that were not in one of theoriginal patterns. So l contains sets with matching positions from a finite collection
and, as each set can only generate a finite number of next states all of which are to theright, the total length of l is bounded and the algorithm must terminate.
The tree and dag automata clearly accept the same language and the automaton isminimal, in the sense that, by construction, none of the matching sets labelling thestates in the automaton are equivalent. We now illustrate the algorithm.
Example 5.2: When applied to the pattern set of Example 3.5, the algorithm generates
the same matching sets as in Figure 3.6, and we number the sets as there. It is clear
from that figure that matching sets which are equivalent have been given the same
number (with different bracketed subscripts for different occurrences) whereas
inequivalent sets have different numbers. The left-to-right order by the matchingposition is given in Figure 5.3.
Matching position

List of states

Λ
1
1.1
1.2
2
3
4
∞

0
1
2
5, 6
3, 4, 78, 9, 10
11, 12, 13
14, 15, 16

Figure 5.3: States of Figure 3.6 with their Matching Positions.

Nedjah, Walter & Eldridge, Optimal Pattern-Matching Automata

281

One possible final list l which preserves this order is therefore given by reading itfrom top to bottom: (0, 1, 2, 5, 6, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16). As each statein this list becomes the current state, it is readily seen that the new states it generates(as given by the transitions from the current state in Figure 3.6) are further along thelist because their matching positions are further to the right. In fact, the states arenumbered in order of creation in this list: State 0 generates state 1 which in turngenerates states 2, 3 and 4. Then state 2 generates states 5 and 6 which are to the leftof 3 and 4 and so are inserted before them. Next, state 5 generates a state which isfound to be equivalent to 4, so that in the dag there will be a transition to state 4 fromboth states 1 and 5. The process continues until the final states 14, 15 and 16 arereached (one for each initial pattern) when the algorithm terminates and the dag
automaton of Figure 4.2 is obtained.

6. Checking for Equivalence
In this section, we show how matching sets can frequently be discriminated easily sothat the cost of checking for equivalence is reduced. However, in some cases,
comparison of suffixes in the matching sets cannot be avoided. We look at threeproperties to help achieve this. One is the set of rules represented by patterns in thematching set, another is the matching position and the third is a state weight function
wt. The first and last yield the same values for equivalent states. We must extend thearity notation #f to include variable symbols and ω which are all considered to be likeconstants and so of arity 0, i.e., #ω = 0.
Definition 6.1: The weight wt of a string of function and variable symbols si is:
wt(s1 ... sn) = 1 + ∑in=1 (# si − 1)for n ≥ 0

and the weight of a matching item α•β is defined as the weight of its prefix, viz.
wt(α•β) = wt(α).
The following properties are readily verified (e.g. part (iii) by structural induction):
Lemma 6.2:i) wt(ε)= 1ii) wt(α1α2...αn ) =iii) wt(t)iv) wt(α•β)v) wt(σ(α))

i.e. the weight of the empty string is 1.

1 + ∑in=1 ( wt (α i ) − 1) for any n strings α1, α2, ..., αn.

= 0for any term t.
= n
if β = t1...tn is a string of n terms.
= wt(α) for any string α and substitution σ.

Using the arities as given previously to our example function symbols, we have forexample:wt(fag•ωaab)= 1 + (#f−1) + (#a−1) + (#g−1) = 1 + 3 −1 + 1 = 4
wt(fafab•ωaab) = 1 + (#f−1) + (#a−1) + (#f−1) + (#a−1) + (#b−1) = 4
So the weight obtained is indeed the number of individual subterms after the matchingdot. As symbol strings or as sequences of terms, these suffixes are identical although
their parent patterns have different structures. For a matching item α•β, β is always asequence of terms and so the weight function represents the number of terms in thesuffix that have not yet been checked. This is the number of disconnected subtrees left
after deleting the prefix nodes from the parse tree of the original term.

282

Lecture Notes in Computer Science, vol. 1298, pp. 273-286, Springer, 1997.

Since the prefix is an invariant of a matching set M, so is the weight and we cansafely write wt(M) for the common weight of any item in M. By (iv), the weight isdetermined uniquely from any suffix. So, as equivalent sets have the same suffix sets,
the weight of a matching set is an invariant of its equivalence class. Equivalent
matching sets must also have the same subsets of rules represented in their patterns.
Lemma 6.3: Equivalent matching sets have the same weight and rule sets.
In Figure 4.2, all inequivalent matching sets are distinguished by the use of either
the weight function or the rule set. Thus the criteria are useful in practice. However,they will clearly not be sufficient in general. In the opposite direction, it is also
sometimes easy to establish equivalence. Combining these with the matching position,
we have the following very useful result which enables the direct checking ofequivalence to be avoided entirely in Example 3.5.
Theorem 6.4: Matching sets that share a common matching position, weight and rule
set are equivalent.
Proof: It suffices show the kernels of the matching sets are equivalent, since then thefunction close will add equivalent items to both sets. Let M1 and M2 be two matchingsets that share the same weight, rule set and common matching position p. Let i1 =r:α1•β1 and i2 = r:α2•β2 be any two items associated with the same rule in theirrespectively kernels. The definitions of accept and close guarantee that the suffixes
consist of a suffix of the original pattern πr of the rule preceded by a number of copiesof ω. To identify this suffix, let p′ be the maximal prefix of the position p
corresponding to a symbol in πr. This is either the whole of p or is the position of avariable symbol ω. Either way, substitutions made by close for variables before p′ ineither i1 or i2 have already been fully passed in the prefix, and no substitution has yet
been made for any variable further on in πr. So if β is the suffix of πr that starts at p′nnthen the items i1 and i2 must have the form α1•ω 1β and α2•ω 2β for some n1, n2 ≥ 0.
Since M1 and M2 have equal weight, we have wt(α1) = wt(α2). So n1 = n2 by Lemma
6.2(iv) and i1 and i2 are equivalent. We conclude that M1 and M2 are equivalent.
Although matching sets that share these three properties are equivalent, thematching positions of equivalent matching sets are not necessarily identical. An
example can be found elsewhere (see [8]). Finally, we observe what weights andmatching positions are possible:
Theorem 6.5: The weight and matching position of any matching set are the same as
those of some matching item consisting of an original pattern with a matching dot.
Proof: From the definition of close, every symbol in an added pattern has the same
position as a symbol in some pattern of the generating set. When that position
becomes the matching position in the two corresponding patterns, the resulting items
will have the same weight. By induction, these positions and weights must occur inthe original pattern set.

Nedjah, Walter & Eldridge, Optimal Pattern-Matching Automata

283

7. Complexity
In this last main section, we evaluate the space complexity of the dag automaton by
giving an upper bound for its size in terms of the number of patterns and symbols in
the original pattern set. The bound established considerably improves Gräf’s bound[2]. The height of a tree or dag automaton is the maximum distance from its root to a
final state. The breadth of a tree automaton is the number of its final states, which isthe size of the closure L . Gräf bounds the size of the tree automaton by showing thatheight(Atree) ≤ ∑π∈L|π| and breadth(Atree) ≤ Ππ∈L(|π|+1)
and then using the fact that the automaton size is less than the product of its breadthand height. We need a generalisation of breadth which is applicable to the dag
automata here. We choose a rightmost matching position for each dag state so that
positions move rightwards along every path. The following definition depends on thischoice and so is not an invariant:

Definition 7.1: The breadth of a dag automaton is the maximum number of matchingsets having the same matching position.
This wider definition of breadth coincides with the one for tree automata because:
Lemma 7.2: The maximum number of matching sets with the same matching position
in a tree automaton is always the number of final matching sets, i.e. its breadth as atree.
Proof: Along any branch from initial to final state of the tree automaton, the matchingpositions are all distinct because each state has a position to the right of its parent.
Hence, for every occurrence of a given position in the tree, there is at least one
occurrence of a final position at the end of the branch. Thus, there are at least as many
final states as states with any given matching position.
Lemma 7.3: If Adag is the dag automaton corresponding to the tree automaton Atreethenbreadth(Adag) ≤ breadth(Atree) and height(Adag) = height(Atree).
Proof: The breadth inequality arises because every state in the dag corresponds tosome state in the tree automaton that has the same assigned position. Also, the heightof the dag and tree automata must coincide since the former has no cycles and so pathsin the tree cannot become shorter in the dag.
The size of the tree automaton is bounded above by the product of its height andbreadth. The nearest equivalent result for dag automata is that its size is bounded by
the product of the number of different matching positions and its breadth. In thefollowing, the bound on the breadth of the dag automaton is much better than thatabove for the tree automaton, and the bound for the number of positions essentially
duplicates the height bound for the tree automaton. So immediately we have a muchbetter overall bound on the size of the dag automaton than that given by Gräf for thetree automaton.
Lemma 7.4: If at least one pattern has 2 or more symbols, then the breadth of the dag
automaton for a pattern set L is bounded above by (2|L|−1)(Maxπ∈L|π|−1) where |π| isthe length of pattern π and |L| is the size (cardinality) of L.

284

Lecture Notes in Computer Science, vol. 1298, pp. 273-286, Springer, 1997.

Proof: There is only one state, the initial one, which has the initial position and there
are exactly |L| states which have the final position, one for each pattern of L. So thebreadth bound holds for them. Otherwise assume that the breadth is determined by a
non-initial, non-final position. By Theorem 6.4, the maximum number of inequivalentstates with the same matching position is bounded by the product of the number ofdifferent possible weights and the number of different possible rule sets. The rule set
for any state could be any non-empty subset of L, of which there are 2|L|−1. So it
remains to show that Maxπ∈L|π|−1 is an upper bound on the number of possible
weights. Using Theorem 6.5, the weight of a state is the weight of a prefix of a rule in
L. This is the number of terms that could appear in its suffix. As we ignore initial andfinal positions, the weight is bounded below by 1 and above by one less than thenumber of symbols in the suffix, and hence by the length of the pattern minus 1. So up
to at most Maxπ∈L|π|−1 different weights are possible.
Lemma 7.5: The height of the minimised dag for a pattern set L is bounded above by
2 − |L| + ∑π∈L|π| and the number of its distinct positions is bounded above by
1 + ∑π∈L|π|.
Proof: Along a path from the initial node to a final node, the positions are all distinct,
each child having a position to the right of its parent, with each position appearing insome pattern of L. The number of non-initial, non-final positions counting
multiplicities is ∑π∈L(|π|−1). Adding 1+|L| to this gives an upper bound on the total
number of distinct positions, whereas adding 2 gives an upper bound on the height ofthe dag.
Combining the methods of proof for these two results above yields a very muchbetter bound on dag automaton size than simply taking the product of breadth andnumber of positions. Our main conclusion about the space efficiency of the dag
automaton described here is the following:
Theorem 7.6: The size of the dag automaton for a pattern set L is bounded above by:|L|

1 + |L| + (2 −1)( ∑π∈L(|π|−1) )Proof: The number of states in the minimised dag automaton is 1+|L| plus the numberof non-initial, non-final states in the dag. By Theorem 6.4, we just need to count the|L|number of possible (weight, position) pairs, and multiply by the bound 2 −1 on thenumber of different possible rule sets. By Theorem 6.5, every (weight, position) pairof interest is given by a non-initial symbol position in an original pattern. So thenumber of such pairs is bounded by the number of such symbols, i.e. by ∑π∈L(|π|−1).
The above bound is easily computable with no internal knowledge of the patterns.
However, if we have more specific information about subsets of rules starting withgiven function symbols, then the following improved bound may be applicable:Nedjah, Walter & Eldridge, Optimal Pattern-Matching Automata

285

Corollary 7.7: The size of the dag automaton for a pattern set L is bounded above by:
1 + |L| + ∑f∈F* { 1 + (2|L\f |−1)( ∑π∈L\f (|π|−1) ) } + δ ( Maxπ∈L|π|−2 )where L\f is as in Definition 2.4, F* is the subset of function symbols which appear as
first symbols in L, and δ = 1 if ω is a pattern of L and L has a pattern of length at least
3, and δ = 0 otherwise.
Proof: Assume, first of all, that ω is not itself a pattern in L. So L = U f ∈F * fL \ f
and |L| = ∑f∈F | L\f |. Then, after the initial state, the automaton splits into disjoint
subautomata Af which are entered according to the symbol f read first. Thus the size ofthe automaton is bounded by the number 1+|L| of initial and final states, plus 1 for the
initial state of each Af plus the number of non-initial, non-final states in each Af . The
rule set available for each state in Af is restricted to a subset of those in L\f and the(weight, position) pairs of states must correspond to symbol positions in patterns of
L\f. So we can apply Theorem 7.6 to bound Af in terms of L\f and so obtain the result.
Now assume that ω is the initial symbol of a pattern. Then it is actually the whole
pattern, so Aω would consist of a single final state. The close function would add
patterns to each Af so that failure to match a pattern of fL\f would result in passing
directly to a sequence of states which recognises all remaining input symbols andterminates at the final state of Aω. For convenience, we will count this sequence ofstates as part of Aω. Then, apart from extra transitions, the only difference the patternω makes is to add Aω, which has at most Maxπ∈L|π|−2 non-final states.

8. Conclusion
First, we described a practical method that compiles a set of prioritised overlapping
patterns into an equivalent deterministic automaton which does not need backtracking
to announce a match. Re-examination of symbols while matching terms is completely
avoided. The matching automaton can be used to drive the pattern-matching processwith any rewriting strategy.
In the main body of the paper, we described a method to generate an equivalent
minimised dag matching automaton very efficiently without constructing the tree
automaton first. We directly built the dag-based automaton by identifying the states of
the tree-based automaton that would generate identical subautomata. By using the dagbased automata we can implement left-to-right pattern-matchers that avoid symbol reexamination without much increase in the space requirements.
Some useful functions were described for distinguishing inequivalent states whenbuilding the dag automaton. A theorem which guaranteed equivalence in terms ofseveral simple criteria was then applied to established improved upper bounds on thesize of the dag automaton in terms of just the number of patterns and symbols in theoriginal pattern set. These considerably improve Gräf's previous bounds for the tree
automaton.

286

Lecture Notes in Computer Science, vol. 1298, pp. 273-286, Springer, 1997.

References[1] Aho, A.V., Sethi, R. and Ulmann, J.D., Compilers: Principles, Techniques andTools, Addison-Wesley Publishing Company, 1986.
[2] Gräf, A., “Left-to-Right Pattern-Matching”, in Proc. Rewriting Techniques andApplications, Lecture Notes in Computer Science, Vol. 488, pp. 323-334, Springer
Verlag, 1991.
[3] Hoffman, C.M. and O’Donnell, M.J., “Pattern-Matching in Trees”, Journal of theACM, Vol 29, pp. 68-95, January 1982.
[4] Hoffman, C.M., O’Donnell, M.J. and Strandth, R.I., “Programming with
Equations”, Software, Practice and Experience, Vol. 15, No 12, pp. 1185-1204,
December 1985.
[5] Johnson, S. C., Yacc - Yet Another Compiler Compiler, Computing Science
Technical Report 32, AT&T Laboratories, Murray Hill, N. J., 1975.
[6] Kennaway, J. R., “The Specificity Rule for Lazy Pattern Matching in Ambiguous
Term Rewriting Systems”, Proc. 3rd European Symposium on Programming,
Lecture Notes in Computer Science, Vol. 432, pp. 256-270, Springer -Verlag,
1990.
[7] Knuth, D.E., Morris, J. and Pratt, V., “Fast Pattern-Matching in Strings”, SIAM
Journal, Vol. 6, No. 2, pp. 323-350, 1977.
[8] Nedjah, Pattern-Matching Automata for Efficient Evaluation in Equational
Programming, PhD Thesis, UMIST, Manchester, UK, 1997.
[9] Nedjah, N., Walter, C.D. and Eldridge, S.E., Efficient Automaton-Driven PatternMatching for Equational Programs, Technical Report, Computation Dept.,
UMIST, Manchester, UK, 1996.
[10] O’Donnell, M.J., Equational Logic as a Programming Language, The MIT Press,
1985.
[11] Sekar, R.C., Ramesh, R. and Ramakrishnan, I.V., “Adaptive Pattern Matching”,
SIAM Journal of Computing, Vol. 24, No. 5, pp. 1207-1234, December 1995.