Strong equivalence of qualitative optimization problems

We introduce the framework of qualitative optimization prob-lems (or, simply, optimization problems) to represent prefer-ence theories. The formalism uses separate modules to de-scribe the space of outcomes to be compared (the generator) and the preferences on outcomes (the selector). We consider two types of optimization problems. They differ in the way the generator, which we model by a propositional theory, is interpreted: by the standard propositional logic semantics, and by the equilibrium-model (answer-set) semantics. Un-der the latter interpretation of generators, optimization prob-lems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of opti-mization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of op-timization problems that can be used as extensions and es-tablish the complexity of associated reasoning tasks. Under-standing strong equivalence is essential for modular repre-sentation of optimization problems and rewriting techniques to simplify them without changing their inherent properties