A new logic for jointly representing hard and soft constraints

Soft constraints play a major role in AI, since they allow to restrict the set of possible worlds (obtained from hard constraints) to a small fraction of preferred or most plausible states. Only a few formalisms fully integrate soft and hard constraints. A prominent example is Qualitative Choice Logic (QCL), where propositional logic is augmented by a dedicated connective and preferred models are discriminated via acceptance degress determined by this connective. In this work, we follow an analogous approach in terms of syntax but propose an alternative semantics. The key idea is to assign to formulas a set of models plus a partial relation on these models. Preferred models are then obtained from this partial relation. We investigate properties of our logic which demonstrate that our semantics shows some favorable behavior compared to QCL. Moreover, we provide a partial complexity analysis of our logic.