**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Sun, 01 May 2016 21:26:59 *

Bäckström, C. (1995).
** Expressive
Equivalence of Planning Formalisms**.
Technical Report LiTH-IDA-R-95-03, Department of Computer and Information
Science, Linköping University, Sweden.
(bibtex),

**Abstract: **A concept of expressive equivalence for planning
formalisms based on polynomial transformations is defined. It is argued that
this definition is reasonable and useful both from a theoretical and from a
practical perspective; if two languages are equivalent, then theoretical
results carry over and, more practically, we can model an application problem
in one language and then easily use a planner for the other language. In
order to cope with the problem of exponentially sized solutions for planning
problems an even stronger concept of expressive equivalence is introduced,
using the novel {\em ESP-reduction}. Four different formalisms for
propositional planning are then analyzed, namely two variants of STRIPS,
ground TWEAK and the SAS$^+$ formalism. Although these may seem to exhibit
different degrees of expressive power, it is proven that they are, in fact,
expressively equivalent under ESP-reduction. This means that neither negative
goals, partial initial states nor multi-valued state variables increase the
expressiveness of `standard' propositional STRIPS.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*