TY - JOUR
T1 - Strong equivalence of qualitative optimization problems
AU - Faber, Wolfgang
AU - Truszczynski, Miroslaw
AU - Woltran, Stefan
PY - 2013
Y1 - 2013
N2 - We introduce the framework of qualitative optimization problems (or, simply, optimization problems) to represent preference theories. The formalism uses separate modules to describe 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. Under the latter interpretation of generators, optimization problems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of optimization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of optimization problems that can be used as extensions and establish the complexity of associated reasoning tasks. Understanding strong equivalence is essential for modular representation of optimization problems and rewriting techniques to simplify them without changing their inherent properties.
AB - We introduce the framework of qualitative optimization problems (or, simply, optimization problems) to represent preference theories. The formalism uses separate modules to describe 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. Under the latter interpretation of generators, optimization problems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of optimization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of optimization problems that can be used as extensions and establish the complexity of associated reasoning tasks. Understanding strong equivalence is essential for modular representation of optimization problems and rewriting techniques to simplify them without changing their inherent properties.
UR - http://www.scopus.com/inward/record.url?scp=84879946134&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84879946134&partnerID=8YFLogxK
U2 - 10.1613/jair.3991
DO - 10.1613/jair.3991
M3 - Article
AN - SCOPUS:84879946134
SN - 1076-9757
VL - 47
SP - 351
EP - 391
JO - Journal of Artificial Intelligence Research
JF - Journal of Artificial Intelligence Research
ER -