The complexity of plan rewriting in PbR originates from two sources: matching the rule antecedent against the plan, and computing the embeddings of the replacement plan. In order to analyze the complexity of matching plan-rewriting rules, we introduce the following database-theoretic definitions of complexity [2]:
Data Complexity: complexity of evaluating a fixed query for variable database inputs.
Expression Complexity: complexity of evaluating, on a fixed database instance, the queries specifiable in a given query language.
Data complexity measures the complexity with respect to the size of the database. Expression complexity measures the complexity with respect to the size of the queries (taken from a given language). In our case, the database is the steps and links of the plan and the queries are the antecedents of the plan-rewriting rules.
Formally, the language of the rule antecedents described in Section 3.1.1 is conjunctive queries with interpreted predicates. The worst-case combined data and expression complexity of conjunctive queries is exponential [2]. That is, if the size of the query (rule antecedent) and the size of the database (plan) grow simultaneously, there is little hope of matching efficiently. Fortunately, relationally-complete languages have a data complexity contained in Logarithmic Space, which is, in turn, contained in Polynomial Time [2]. Thus our conjunctive query language has at most this complexity. This is a very encouraging result that shows that the cost of evaluating a fixed query grows very slowly as the database size increases. For PbR this means that matching the antecedent of the rules is not strongly affected by the size of the plans. Moreover, in our experience useful rule antecedents are not very large and contain many constant labels (at least, the node and edge predicate names) that help to reduce the size of the intermediate results and improve the efficiency of matching. This result also indicates that we could extend the language of the antecedent to be relationally complete without affecting significantly the performance of the system.11 Another possible extension is to use datalog with stratified negation, which also has polynomial time data complexity. Graph-theoretic properties of our plans could be easily described in datalog. For example, the possibly-adjacent interpreted predicate of Figure 7 could be described declaratively as a datalog program instead of a piece of code. In summary, rule match for moderately sized rules, even for quite expressive languages and large plans, remains tractable and can be made efficient using production match [32] and query optimization techniques [74].
The second source of complexity is computing the embeddings of the replacement plan given in the consequent of a plan-rewriting rule. By the definition of full-specification rules, the embedding is completely specified in the rule itself. Thus, it suffices simply to remove the undesired subplan and directly add the replacement subplan. This is linear in the size of the consequent.
For partial-specification rules, computing all the embeddings of the
replacement subplan can be exponential in the size of the plan in the
worst case. However, this occurs only in pathological cases. For
example, consider the plan in Figure 15(a) in which we are
going to compute the embeddings of step x into the remainder of
the plan in order to satisfy the open precondition g0. Step x has no preconditions and has two effects 
b and g0. Each step in the plan has proposition b as an
effect. Therefore, the new step x conflicts with every step in
the plan (1 to n) and has to be ordered with respect to
these steps. Unfortunately, there are an exponential number of
orderings. In effect, the orderings imposed by adding the step x
correspond to all the partitions of the set of steps (1 to
n) into two sets: one ordered before x and one
after. Figure 15(b) shows one of the possible
orderings. If the subplan we were embedding contained several steps
that contained similar conflicts the problem would be compounded.
Even deciding if a single embedding exists is NP-hard. For example, if
we add two additional effects 
a and 
g1 to
operator x, there is no valid embedding. In the worst case
(solving first the flaws induced by the conflicts on proposition b) we have to explore an exponential number of positions for step
x in the plan, all of which end up in failure.
Nevertheless, given the quasi-decomposability of useful planning
domains we expect the number of conflicts to be relatively small. Also
most of the useful rewriting rules specify replacement subplans that
are small compared with the plan they are embedding into.
Our experience indicates that plan rewriting with
partial-specification rules can be performed efficiently as shown by
the results of Section 4.
