FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems

Authors: Alireza Ensan, Eugenia Ternovska and Heng Liu

Paper Information

Title:A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems
Authors:Alireza Ensan, Eugenia Ternovska and Heng Liu
Proceedings:PRUV PRUV 2018 Proceedings
Editors: Thomas Lukasiewicz, Rafael PeƱaloza and Anni-Yasmin Turhan
Keywords:Preference Modeling, Declarative Programming, Model Theory, Model Expansion
Abstract:

ABSTRACT. Automated decision making often requires solving difficult and primarily NP-hard problems. In many AI applications (e.g., planning, robotics, recommender systems), users can assist decision making by specifying their preferences over some domain of interest. To take preferences into account, we take a model-theoretic approach to both computations and preferences. Computational problems are characterized as model expansion, that is the logical task of expanding an input structure to satisfy a specification. \ignore{Preferences are represented as partial orders on domain elements and then lifted to orders on tuples and then structures.} The uniformity of the model-theoretic approach allows us to link preferences and computations by introducing a framework of a prioritized model expansion. The main technical contribution is an analysis of the impact of preferences on the computational complexity of model expansion. We also study an application of our framework for the case where some information about preferences is missing. Finally, we discuss how prioritized model expansion can be related to other preference-based declarative programming paradigms.

Pages:16
Talk:Jul 19 16:00 (Session 136D: PRUV regular papers)
Paper: