
| I                 | 277                     | initial state description                                                 |              |
|-------------------|-------------------------|---------------------------------------------------------------------------|--------------|
| f                 | 282                     | compilation scheme (                                                      | hf ; fi; fg ; ti; tg i)              |
| F                    | 282                     | transformation induced by compilation scheme                              |              |
| f ; fi; fg                   | 282                     | components of a compilation scheme                                        |              |
| G                 | 277                     | goal of a planning task                                                   |              |
| 274               | set of boolean formulae |                                                                           |              |
| ; ';              | 273                     | boolean formulae                                                          |              |
| l                 | 287                     | literal                                                                   |              |
| L; K              | 273                     | sets of literals                                                          |              |
|                    | 273                     | all boolean formulae that use atoms from                                  |              |
| Mod                    | 274                     | set of all models of a theory                                             |              |
| NC1               | 298                     | complexity class                                                          |              |
| neg                    | 273                     | negative literals in a set of literals                                    |              |
| NP                | 272                     | complexity class                                                          |              |
| NP/poly           | 295                     | non-uniform NP                                                            |              |
| o                 | 274                     | operator (                                                                | hpre; posti) |
| O                 | 276                     | set of operators                                                          |              |
| O?                | 277                     | set of finite sequences of operators                                      |              |
| p; q; u; v; x 274 | propositional atoms     |                                                                           |              |
| P ;                    | 275                     | potentially active effects of an operator for a given state specification |              |
| P                 | 272                     | complexity class                                                          |              |
| P/poly            | 295                     | non-uniform P                                                             |              |
| PH                | 295                     | the polynomial hierarchy                                                  |              |
| pos                    | 273                     | positive literals in a set of literals                                    |              |
| PLANEX            | 279                     | plan existence problem                                                    |              |
| post              | 274                     | postconditions of an operator                                             |              |
| pre               | 274                     | preconditions of an operator                                              |              |
| PSPACE            | 272                     | complexity class                                                          |              |
| 277               | planning instance (     | h                                                                         | ; I; Gi)     |
| i                 | 295                     | complexity class in the polynomial hierarchy                              |              |
| p                 |                         |                                                                           |              |
| R ;                    | 276                     | maps a state specification and an operator to a new state                 |              |
| Res ;                    | 277                     | extension of R ;                                                                            | to plans     |
| s                 | 274                     | state (or truth assignment)                                               |              |
| S                 | 274                     | state specification                                                       |              |
| S                 | 278                     | the STRIPS planning formalism                                             |              |
| S                 | 278                     | STRIPS with literals in preconditions                                     |              |
| S                 | 278                     | STRIPS with boolean formulae in preconditions                             |              |
| S                 | 278                     | STRIPS with incomplete state descriptions                                 |              |
| S                 | 278                     | STRIPS with conditional effects                                           |              |
| S:::              | 278                     | STRIPS with combinations of the above extensions                          |              |
| SLIC              | 283                     | equivalence classes induced by 1                                                                           |              |
| SLI               | 283                     | equivalence classes induced by 1 p                                                                           |              |
|                     | 273                     | all propositional atoms used in a set of literals p                       |              |
|                    | 273                     | countably infinite set of propositional atoms                             |              |
