In other words, whenever R S; o results in a "legal" specification, this specification describes the states that result from the application of the state-transition function o to the states that satisfy the original state specification S. Further, if R S; o is illegal, there are good reasons for it.

A **planning instance** is a tuple h ; I; Gi; where h ; Oi is the **domain structure** consisting of a finite set of propositional atoms and a finite set of operators O,

## I  Is The Initial State Specification, And G  Is The Goal Specification. 4

When we talk about the **size of an instance**, symbolically jj jj, in the following, we mean the size of a (reasonable) encoding of the instance.

In the following, we use the notation O?to refer to the **set of finite sequences** of operators.

Elements of O?are called **plans**. Then jj jj denotes the size of the plan, i.e., the number of operators in . We say that is a c**-step plan** if jj jj  c. The result of applying to a state specification S is recursively defined as follows:

$Res$$S,\left\langle\right\rangle$$S$$Res$$S,\left\langle o_{1},o_{2},\ldots,o_{n}\right\rangle$$Res$$R$$S,o_{1}$$\left\langle o_{2},\ldots,o_{n}\right\rangle$
$${\mathrm{or~a~solution~of}}\quad{\mathrm{iff}}$$

$$\mathbf{G}.$$
A sequence of operators is said to be a **plan for** or a **solution of** iff

1. Res I; ) 6j and
$$2.\;\;R e s\;\;{\bf I}_{,}$$
2. Res I; ) G.
Example 3 Let and O be the propositional atoms and operators introduced in Example 1 and consider the following planning instance: hh ; Oi; tex; bib; ind ; dvi; dvi cite okgi: In words, given a latex source file (tex*) and a bibliography database (*bib), we want to generate a dvi file (dvi*) such that the citations in this file are correct (*dvi cite ok). Furthermore, we do not know anything about the existence of a bbl-file or aux-file etc., but we know that there is no index file yet
( ind*). The plan* hbibtex; latexi is a solution of because the plan does not result in an illegal state specification and the resulting state specification entails dvi and dvi cite ok.

Plans satisfying (1) and (2) above are "sound." In order to state this more precisely, we extend the notion of state transition functions for operators to state transition functions for plans. Let  be the state transition function corresponding to the composition of primitive state-transition functions induced by the operators in ho1; : : : ; oni, i.e.,
 o1;:::;on o1  : : :  on ;