A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems Alireza Ensan1 , Eugenia Ternovska2 , and Heng Liu3 1 Simon Fraser University, Canada aensan@sfu.ca 2 Simon Fraser University, Canada ter@sfu.ca 3 Simon Fraser University, Canada liuhengl@sfu.ca Abstract. Automated decision making often requires solving difficult and pri- marily NP-hard problems. In many AI applications (e.g., planning, robotics, rec- ommender systems), users can assist decision making by specifying their prefer- ences 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 expand- ing an input structure to satisfy a specification. 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 discuss how prioritized model expansion can be re- lated to other preference-based declarative programming paradigms. Finally, we study an application of our framework for the case where some information about preferences is missing. Keywords: Preference Modeling, Model Expansion, Model Theory, Descriptive Complexity 1 Introduction Solving computationally hard problems (e.g., NP-hard) is in the core of many AI tasks. Due to the significant progress in performance of modern solvers, finding solutions of such problems (e.g., planning, travelling salesman, graph colouring, etc.) has become feasible in many applications. Automated reasoning in intelligent systems often gen- erates a multitude of acceptable results. For example, in the context of resource man- agement, consider the prominent problem of Airport Gate Scheduling [14] that, in a nutshell, is the task of assigning flight arrivals and departures to different gates of an airport. The problem can be formalized as a Constraint Satisfaction Problem (CSP). Some variations of the problem are NP-hard and have been encoded as scheduling or clique partitioning that itself can be transformed to graph colouring problem [4]. Model expansion [27] is the logical task of expanding a mathematical structure (a prob- lem instance) to a solution structure that satisfies a formula (problem specification). The 2 A. Ensan et al. formula can be written in any specification language with a model-theoretic semantics. The authors showed that other declarative frameworks such as satisfiability problem (SAT), CSP, and answer set programming (ASP) can be encoded as model expansion. By distinguishing between problem instances and problem specifications, model expan- sion provides a robust modelling framework and establishes a connection to Descriptive Complexity [22]. In many industrial applications, a decision maker may be inclined toward a subset of results. The preferred alternatives can be chosen in automated decision making. For instance, in the Airport Gate Scheduling problem, there could be some preferences for scheduling gates. A certain gate may be preferred to be assigned domestic flights rather than international flights. For language-independent solving, it is crucial to connect model expansion to a preference framework. Since preferences play a key role in AI, a large number of frameworks for handling preferences have been proposed during the last two decades such as [8, 23, 7, 21, 5, 28, 26]. These proposals are often language-dependent because they are added to a host formal language such as ASP [8, 13] or default logic [12]. In this paper, we propose a model-theoretic approach to handle preferences associated to a model expansion. The main motivation of our work is to connect model theory, descriptive complexity, and preference modelling to study computationally hard opti- mization problems. To the best our knowledge this is the first proposal of this kind in the literature. We aim to construct a language-independent preference framework that can be added to any declarative language (e.g., SAT, CSP, and ASP) which can be en- coded as a model expansion. Toward this goal, we introduce the notion of a prioritized model expansion that extends model expansion by adding a set of preferences of a de- cision maker. Preferences can be expressed as priorities over ground atoms and then generalized to structures. Using a model-theoretic approach has promising advantages from both modelling and application viewpoints. For the modelling purposes, properties of model theory [10] can be used to identify certain syntactic fragments of a logic for answering tractable queries with preferences. Moreover, given that model expansion underlines all predominant declarative frameworks such as ASP, SAT, and CSP, prioritized model expansion can model the main preference-based declarative frameworks such as [8], [33], etc. From a practical perspective, by viewing preferences as first order structures, we can use model theory to study properties of preferences and deal with practical cases in declarative programs such as when some information is missing (similar to null values in database systems). We do it by introducing the notion of an incomplete preference term that pri- oritizes some domain elements when some values are unknown. For example, in Airport Gate Scheduling, a decision maker states that gate number 2 is not the worst option for domestic flights, while it is not known what the best option is. We address the problem of finding preferred solutions of search problems in the presence of incomplete prefer- ences. We argue that this problem can be viewed as query answering over incomplete databases. It was demonstrated in [20] that, under some conditions, computing certain answers can equivalently be done using a naive evaluation, that is by evaluating queries directly on incomplete relational databases, by considering unknown values as domain elements. The equivalence is due to the preservation theorems [31]. The main advan- A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 3 tage is that naive evaluations drop the computational complexity of computing certain answers dramatically. A model-theoretic view on modular systems with preferences was presented in [17]. The authors argued that their proposal can express preference statements in other for- malisms such as CP-nets [7]. They used Codd’s relational algebra [11] to combine mod- ules with preferences. The combination was static – the authors did not focus on the model expansion and its computational complexity. Our main contributions are as follows. First, we propose the notion of prioritized model expansion that is a declarative framework for specifying computational problems with preferences. Second, we discuss that adding preference even in the simplest formulation leads to the rise of computational complexity of ΣkP -complete (k th level in the polyno- mial hierarchy) model expansions. Third, we study the relations of some preference- based frameworks with prioritized model expansion. We apply the computational com- plexity result of the task to obtain similar results for those frameworks. Fourth, a method to deal with incomplete information about preferences is proposed. Finally, we show that preservation theorems can be used for finding preferred solutions of problems with incomplete preferences. 2 Background A τ -structure A = (A, R1A , ..., RnA ) is a tuple where τ = {R1 , ..., Rn } is a relational vocabulary that is a set of non-logical relation symbols Ri with associated arity ki , A is a domain, and for any Ri ∈ τ , RiA is called the interpretation of Ri and RiA ⊆ Aki . For a formula ψ in any logic L, vocab(ψ) denotes the set of vocabulary symbols that appear in ψ. A boolean query Q over τ -structures is defined as a mapping from the set of all τ -structures to {0,1}. A boolean query Q can be related to a model checking task such that for a formula ϕ in logic L and vocab(ϕ) = τ , Qϕ (A) = 1 if and only if A |= ϕ where A is a τ -structure. Model expansion (MX) is the task of expanding a structure to satisfy a formula in any logic L [27]. Let us fix a finite relational vocabulary τ and a domain Dom. Definition 1 (Model Expansion MXIσ ,ψ ) Input: formula ψ in logic L, input vocabulary σ ⊆ vocab(ψ), and a σ-structure I over domain Dom, Find a structure A where A |= ψ and expands I. (The decision version: is there a structure A such that A |= ψ and A expands I?) We call A an expansion structure of MXIσ ,ψ . Any expansion structure A is a τ - structure with domain Dom. For any logic L, the data complexity of (the decision version of) model expansion (MX) is always in-between model checking (MC) and satisfiability (SAT). For example, for first-order logic, MC is AC0 , MX is NP-complete, SAT is undecidable. The combined complexity of model expansion for first-order logic is NEXPTIME. A complexity anal- ysis of the three tasks (MC, MX, SAT) for several logics of interest was performed in [24]. Note that, when the input vocabulary is empty, MX is often called model genera- tion, and if the input vocabulary is equal to the vocabulary of formula ψ, it is equivalent to model checking. 4 A. Ensan et al. A variety of problems in AI such as the Airport Gate Scheduling problem can be re- duced to graph colouring that is a widely discussed NP-hard problem. Graph colouring can be characterized as a first-order model expansion ( i.e, the problem specification is in first-order logic) as follows. Example 1 Let binary relation E denotes edges relation between vertices and unary relation symbols R, G, and B denote red, green, and blue colours respectively. The formula ψ specifies three-graph colouring ψ = ∀x [(R(x) ∨ B(x) ∨ G(x)) ∧¬((R(x) ∧ B(x)) ∨ (R(x) ∧ G(x)) ∨ (B(x) ∧ G(x)))] ∧ ∀x∀y [E(x, y) ⊃ (¬(R(x) ∧ R(y)) ∧¬(B(x) ∧ B(y)) ∧ ¬(G(x) ∧ G(y)))]. A graph G = (V, E) is an instance structure with vocabulary σ = {E} and domain V that is the set of vertices. The model expansion MXGE ,ψ finds expansion structure A (i.e., three-colouring of G) that interprets symbols R, B, and G satisfying ψ. Note that R, B, and G are implicitly second-order-∃ quantified. G z }| { (V ; E G , RA , B A , GA ) |= ψ. | {z } A In order to study the computational aspect of prioritized model expansion, we employ the notion of a Turing machine as the model of computation. Definition 2 Oracle ML is a Turing machine M augmented by an oracle tape that can decide whether some input string x in the oracle tape belongs to a language L. Let X be a complexity class. Notation 1 P X is the class of languages (complexity class) that can be computed by a deterministic Turing machine with an oracle in X. Notation 2 co-X is the complexity class of decision problems whose complements are in X. The polynomial hierarchy (PH) that is a hierarchy of complexity classes is defined as ΣkP ∆P ΣkP P = Σ0P = Π0P = ∆P P 0 , Σk+1 = NP , ∆P k+1 = P k , and Π P k+1 = coNP for k > 0. 3 Prioritized Model Expansion In this section, we introduce the notion of prioritized model expansion which is model expansion with a collection of preferences of a decision maker. To model preferences, we define preference expression as an order over a set of ground atoms. We study the computational complexity of solving problems related to prioritized model expansions including Dominant Structure (i.e., given two structures, whether one is preferred to another), Optimal Expansion (i.e., given a structure, if it is an optimal expansion of a model expansion task), and Goal-Oriented Optimal Expansion (i.e., deciding if there is an optimal expansion satisfying a certain goal). At the end of this section, we define preference term as a generalization of preference expressions. A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 5 3.1 Preference Expression Let us fix a domain Dom. Consider k first order variables x1 , ..., xk over Dom, vocab- ulary τ , and k-ary R ∈ τ . A k-ary tuple a = (a1 , ..., ak ) is an assignment to an ordered set of variables x = (x1 , ..., xk ) such that for 1 ≤ i ≤ k, ai ∈ Dom. We use the symbol a[xi ] to denote value ai . R(a) is called a ground atom where a ∈ Domk . A preference expression P is an order on a set of ground atoms. Definition 3 (Preference Expression) A preference expression P is a pair P = (Sτ , wP ) where Sτ is the set of all ground atoms of vocabulary τ over domain Dom and wP is a preorder on Sτ . For ground atoms R(a) and T (b) where R, T ∈ τ , k-ary tuple a ∈ Domk , and k 0 -ary 0 tuple b ∈ Domk , R(a) wP T (b) is read as R(a) is preferred to T (b). Also, R(a) is called strictly preferred to T (b) with notation R(a) AP T (b) if R(a) wP T (b) is true and T (b) wP R(a) does not hold. Also, R(a) ≈P T (b) if R(a) wP T (b) and T (b) wP R(a). Example 2 Consider a graph G = (V, E) and three colours R, B, and G as in Exam- ple 1. Suppose P = (Sτ , wP ) where domain V = {v1 , v2 , ...vn } is a finite set of nodes, τ = {E, R, G, B}, and R(v1 ) ≈P R(v2 ) AP R(v3 ) states that it is equally preferred to have v1 and v2 with red colour and either of which is strictly preferred to v3 with red colour. Also, G(v2 ) A B(v3 ) denotes that having v2 with green colour is favoured to blue v3 . The relation between ground atoms can be lifted to a preference order among structures. The idea of comparing two sets based on the preference on their members has been widely discussed in different domains such as in database systems [35] and even beyond the realm of theoretical computer science such as in economic studies and decision theories [9]. Inspired by [35, 1], here, we introduce three different methods to construct a relation ≥P from wP among τ -structures with domain Dom as follows. Definition 4 (Preference Relation on Structures) Given a preference expression P = (Sτ , wP ), let A and B be two τ -structures with domain Dom, – Weak Pareto (WP). A ≥wp P B iff for all R, S ∈ τ and for all a ∈ R A and all B b ∈ S , R(a) wP S(b). B – Upper Bound Dominance (UBD). A ≥ubd P B iff for all S ∈ τ and for all b ∈ S , A for some R ∈ τ , there is a such that a ∈ R and R(a) wP S(b). B – Element Dominance (ED) A ≥ed P B iff for some R, S ∈ τ , there is b ∈ S and A there is a ∈ R such that R(a) wP S(b) and there is not c for some T ∈ τ such that c ∈ T B and T (c) AP R(a). To build a one-to-one correspondence between our preference model and other pref- erence frameworks in the literature, e.g., [35], [34], [8], etc, we use one of preference semantics Weak Pareto, Upper Bound Dominance, or Element Dominance. Defining these different semantics contributes to the flexibility and generality of our proposal in 6 A. Ensan et al. which a variety of optimization problems can be encoded. We discuss this generality in more details in section 4. The strict version of ≥yP where y ∈ {wp, ubd, ed} is defined as A >yP B if A ≥yP B and B ≥yP A does not hold. A is dominant to B based on semantics y where y ∈ {wp, ubd, ed} when A >yP B. Also, we say A is dominant to B with notation A >P B when there is y ∈ { wp, ubd, ed} such that A >yP B. The problem of deciding if A is dominant is called Dominant Structure problem that is characterized as follows. Definition 5 (Dominant Structure) Input: a preference expression P = (Sτ , wP ) and τ -structures A and B with domain Dom, Question: is A >P B? Proposition 1 Solving Dominant Structure problem is polynomial in the size of Dom. Proof. As stated by Definition 4, at most, we compare all tuples in RA and RB for all R ∈ τ . The total possible number of k-ary tuples is |Dom|k where k is the maximum arity of predicate symbols in τ . Therefore, O(|Dom|2k ) comparisons are required for each R ∈ τ . Thus, deciding if A >P B is in m · O(|Dom|2k ) (polynomial in the size of Dom) where m is the number of elements in τ . We remark that the vocabulary τ is fixed and our discussion on computational complex- ity is focused on data complexity. 3.2 Prioritized Model Expansion A prioritized model expansion (PMX) is the problem of finding the most preferred expansion structures with respect to preferences. Definition 6 (Prioritized Model Expansion) Input: a formula ψ, input vocabulary σ ⊆ vocab(ψ), a σ-structure I, and a preference expression P = (Sτ , wP ), Find structure A such that A is an expansion structure of MXIσ ,ψ and there is not an expansion structure B such that B >P A. Notation 3 The problem of prioritized model expansion is denoted by ΠIσ ,ψ = (MXIσ ,ψ , P ) where MXIσ ,ψ is a model expansion and P = (Sτ , wP ) is a preference expression. Definition 7 Any solution to a problem of prioritized model expansion ΠIσ ,ψ is called an optimal expansion of ΠIσ ,ψ . In the rest of this subsection, we study some decision problems that can be associated to a prioritized model expansion. The Optimal Expansion problem asks whether a given structure is an optimal expansion of a prioritized model expansion. Definition 8 (Optimal Expansion) Input: a τ -structure A and a prioritized model expansion ΠIσ ,ψ = (MXIσ ,ψ , P ) where τ = vocab(ψ) and P = (Sτ , wP ) is a preference expression. Question: Is A an optimal expansion of ΠIσ ,ψ ? A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 7 Proposition 2 Let model checking of ψ (given a structure A, decide if A |= ψ) in MXIσ ,ψ be in the complexity class Y . Solving the problem of Optimal Expansion is in co-NPY . Proof. The complementary problem is deciding if there is an expansion structure B such that B >P A. The complementary problem can be solved by a non-deterministic polynomial Turing machine guessing B with access to an oracle in Y that decides if B is an expansion of MXIσ ,ψ (that includes checking if B expands I in polynomial time and if B |= ψ in the complexity Y ) and based on Proposition 1, in polynomial time checks if B >P A. Thus, the complementary problem is in NPY and the original problem is in co-NPY . One of the common tasks in many AI applications is to determine if a certain goal is achieved by solutions of a problem, e.g., in planning [3]. In the context of prioritized model expansion, it can be translated into whether there is an optimal expansion that satisfies a formula. The problem is formulated as follows. Definition 9 (Goal-Oriented Optimal Expansion) Input: a prioritized model expansion ΠIσ ,ψ = (MXIσ ,ψ , P ) where τ = vocab(ψ) and P = (Sτ , wP ) is a preference expression, and a formula φ such that φ is of the form R1 (a1 ) ∧ ... ∧ Rl (al ) where Ri ∈ τ and Ri (ai ) is a ground atom for 1 ≤ i ≤ l. Question: Is there an optimal expansion A of ΠIσ ,ψ such that A |= φ? Proposition 3 Let solving the Optimal Expansion problem of ΠIσ ,ψ = (MXIσ ,ψ , P ) be in the complexity class X. Solving the problem of Goal-Oriented Optimal Expansion is in NPX . Proof. First, we non-deterministically guess a τ -structure A and in polynomial time check if ai ∈ RiA , for 1 ≤ i ≤ l, that can be done by means of a non-deterministic polynomial Turing machine. Second, we check whether our guess is an optimal expan- sion that is in the complexity class X by the assumption. Thus, the problem can be solved by a non-deterministic polynomial Turing machine using an oracle in X. Hence, the problem is in NPX . Goal-Oriented Optimal Expansion problem can be generalized to finding an optimal expansion that satisfies a formula φ in a logic L∗ . In this case, the complexity of model checking in logic L∗ (i.e., given a structure A if A |= φ?) taken into account. However, for the sake of simplicity, in this paper, we consider the goal φ as a conjunction of ground atoms and it can be verified in polynomial time if a structure A satisfies φ. It was discussed in [27] that any boolean query computable in NP can be expressed as a first order model expansion MXIσ ,ψ where ψ is a first order formula. Based on Fagin’s theorem [18], NP is the class of boolean queries expressible in existential second order logic (∃SO). This shows that a first order MX and existential second order logic have the same expressive power. Similarly, the polynomial hierarchy is the set of boolean queries expressible in second order logic and any query computable in ΣkP can be encoded as MXIσ ,ψ where ψ is a formula of the form Q1 , ..., Qk−1 ψ ∗ such that for 1 ≤ i ≤ k, Qi is a second order quantifier where Qi = ∀ for k is odd and Q = ∃ otherwise, and 8 A. Ensan et al. ψ ∗ is a first order formula. Therefore, when a decision version of a model expansion MXIσ ,ψ is in ΣkP , model checking of ψ is in Πk−1 P and based on Proposition 2, solving P Optimal Expansion (MXIσ ,ψ , P ) is in Σk . The following result shows the impact of introducing preferences on Goal-Oriented Optimal Expansion for ΣkP -complete model expansions. Theorem 1 Let the decision version of a model expansion be ΣkP -complete. The prob- P lem of Goal-Oriented Expansion Structure is Σk+1 -complete. P Proof. The membership to Σk+1 follows from the results of Proposition 2, Proposi- tion 3, and properties of model expansion. Since the model expansion is in ΣkP , the P complexity of model checking of ψ is in Πk−1 . Therefore, based on proposition 2, P the complexity of Optimal Expansion problem is in co-NPΣk−1 that is equal to ΠkP . P Also, based on Proposition 3, Goal-Oriented Optimal Expansion problem is in NPΠk P or NPΣk that is equal to Σk+1P . For the proof of hardness, we consider the following steps. First, we show that the problem of deciding the existence of minimal solutions of an abductive logic program [15] satisfying a goal can be reduced to Goal-Oriented Opti- mal Expansion similar to preferred logic programs [33]. An abductive logic program is defined as ALP = hH, M, Pi over a set A of propositional atoms where P is a logic program, H ⊆ A is called the hypothesis and M ⊆ A ∪ {¬a|a ∈ A} is the manifesta- tion. A solution to ALP is a set N ⊆ H such that there is a stable model S of P ∪ N and M ⊆ S. A solution N is called (H) minimal if there is not a solution N 0 such that N 0 ⊂ N . For a given hypothesis h ∈ H, deciding if there is a minimal solution N such that h ∈ N is Σ2P -complete. Second, consider an abductive logic program ALP = hH, M, Pi. Let us define a logic program P 0 as a set of rules of the form r : R(a) ← ¬S(b) for any R(a) wP S(b) such that S(b) ∈ H. Rule r indicates the less preferred ground atom (i.e., S(b)) belongs to the set of hypothesis atoms H. Define P ∗ = P ∪ P 0 . The existence of a stable model of a logic program is NP-complete and it can be translated into the decision version of a model expansion as it was shown in [27]. The problem of finding if there is a H minimal solution of ALP can be reduced to deciding whether there is an optimal expansion in (MXI,ψ , P ) where P ∗ is translated into MXI,ψ based on [27]. Assume X1 and X2 are two stable models of P ∗ . If X1 is preferred to X2 with respect to one of preference semantics in Definition 4, there is R(a) ∈ X1 and S(b) ∈ X2 such that R(a) wP S(b). So, we have X1 ∩ H ⊆ X2 ∩ H and therefore, any preferred answer set is H minimal. Hence, finding a minimal solution of hH, M, Pi is equivalent to finding an optimal expansion of ΠIσ ,ψ that satisfies a goal M . Thus, Goal-Oriented Optimal Expansion for a NP-complete MX is Σ2P -complete. Third, for model expansions in the higher levels of the polynomial hierarchy, consider the following. ΣkP -complete problems can be encoded as a combined logic program [6]. Π = (Pg , Pt ) is called a combined logic program where Pg and Pt are logic programs over a set of propositional variables G and T respectively. M is a model of Π if it is a stable model of Pg and there is not a stable model N of Pt such that M ∩ G = N ∩ T . The decision version of this problem is Σ2P -complete. Recursively, the existence of a A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 9 model of a combined program in depth 2 defined as Π2 = (Pg2 , (Pg1 , Pt )) is Σ3P - complete and similarly, in depth k, the existence of a model of (Pgk−1 , Πk−2 ) is ΣkP - complete. We introduce abductive combined program as C = hH, M, Πi where Π = (Pg , Pt ) is a combined logic program. W is a solution of C if there is a model S of (Pg ∪ W, Pt ) such that M ⊆ S. W is minimal if there is not a solution W 0 such that W0 ⊂ W. Lemma 1 The problem of deciding if C = hH, M, Πk i for a given h ∈ H has a P minimal solution containing h is Σk+1 -complete. Proof: The proof includes a translation from a quantified boolean formula (QBF) to C for k = 2 and then by induction on k for k > 2, the result follows. Let ϕ be a boolean formula in CNF and X = {x1 , ..., xm }, W = {w1 , ..., wm }, X 0 = {x01 , ..., x0m }, Y = {y1 , ..., yn }, and Z = {z1 , ..., zl } be a set of boolean variables in ϕ. Let t, h, and f be also boolean variables. Consider Pg as a set of rules of the form {t ← xi , x0i }, {wi ← xi }, {wi ← x0i }, {t ← y1 , ...yn , h}, and{f ← l1 , ..., lr } where ¬(l1 ∧, ..., ∧lr ) ∈ ϕ similar to [15]. For X ∪ X 0 ⊆ H, a H-minimal solution of hH, {t} ∪ W, Pg i does not contain f and it has either xi or x0i . On the other hand, similar to [6], assume Pt determines the truth value of a set of boolean variables Z. Also, for each clause C ∈ ϕ, suppose that Pt includes a set of rules of the form t ← ¬C and f ← ¬f, t that means t must not be in any stable model of Pt . This implies that the validity of ∃X∀Y ∃Zϕ is equivalent to the existence of a H-minimal solution of C that contains h. So, for k = 2, the existence of a minimal solution to an abductive combined logic program containing an atom h is Σ3P -complete. Finally, according to the previous steps and Lemma 1, finding a minimal solution of an abductive combined logic program in level k can be translated into a Goal-Oriented Optimal Expansion where the model expansion is ΣkP -complete and hence the result follows. Theorem 1 presents an important consequence of adding preferences to a ΣkP -complete model expansion. For the problem of deciding if there is an expansion that satisfies a goal φ, adding preferences leads to a jump in the polynomial hierarchy. So, the pref- erence relation between expansion structures derived from a preference expression can not be translated into axiomatization ψ in polynomial time unless P=NP or the polyno- mial hierarchy collapses. Example 3 Consider the problem of graph colouring that was described as model ex- pansion in Example 1. Let G = (V, E) be the input graph where V = {v1 , v2 , v3 , v4 , v5 } and E G = {(v1 , v2 ), (v1 , v3 ), (v2 , v3 ), (v2 , v4 ), (v4 , v5 ), (v3 , v5 )}. Assume that we pre- fer red colour for v1 . Also, v4 with red colour is favoured to v5 with red colour and blue v2 is preferred to green v2 . These preference statements can be encoded by a preference expression P such that R(v1 ) AP B(v1 ) and R(v1 ) AP G(v1 ). Also, R(v4 ) AP R(v5 ) and B(v2 ) AP G(v2 ). The prioritized model expansion ΠG,ψ = (MXG,ψ , P ) where MXG,ψ is the characterization of three-colouring for input graph G and P is the pref- erence expression. The input graph G has 18 possible three-colourings. Among these solutions, A is an optimal expansion of G (based on Element Dominance semantics) where RA = {v1 , v4 }, B A = {v2 , v5 }, and GA = {v3 }. 10 A. Ensan et al. 3.3 Preference Term In this subsection, we extend the notion of a preference expression by introducing pref- erence term that is an order on the domain of a first order variable. Preference terms can be related to the concept of preferences in relational database systems. However, unlike databases [23], where the goal is to find the most preferred records in a table, here we aim to find preferred expansion structures. A preference relation among tu- ples (and therefore among ground atoms that is specified as a preference expression) is derived from a set of preference terms. The usefulness of defining preferences over domains of variables is to deal with incomplete information about preferences that will be discussed in details in Section 5. A preference term p is defined as follows. Definition 10 (Preference Term) A preference term p is a pair p = (A, ) where A is a set and  is a preorder over A. For a, b ∈ A, a  b means that a is preferred to b. Also, a ∼ b if a  b and b  a. Moreover, a  b (a is strictly preferred to b) when a  b and b  a does not hold. Consider first order variables x1 , ..., xk . The symbol dom(x) denotes the domain of x. Assume we are given k preference terms px1 = (dom(x1 ), 1 ), ..., pxk = (dom(xk ), k ). A preference relation  over k-ary tuples a and b is constructed from px1 , ..., pxk as follows. Definition 11 (Preference Relation on Tuples) Given a set of preference terms P = {px1 , ..., pxk } and two k-ary tuples a and b, we say that a is preferred to b with respect to P, notation a P b, iff for all pi ∈ P, a[xi ] i b[xi ]. A preference expression P can be constructed from a set of preference terms P such that for a predicate symbol R, R(a) wP R(b) if and only if a P b. Prioritized model expansion then is extended to ΠIσ , ψ = (MXIσ ,ψ , P) where ≥P is derived from a set of preference terms and the semantics of optimal expansion is exactly as before. 4 Prioritized Model Expansion and Declarative Specifications of Optimization Problems In this section we study some examples of declarative specification of optimization problems that can be encoded as a prioritized model expansion and the associated com- putational complexity can be determined by the result of Theorem 1. First, consider a prioritized logic program (PLP) [33] as one of the first examples of logic programming with preferences. A PLP is a pair (P r, Φ) where P r is a standard logic program with stable model semantics and Φ is a set of preference relations among atoms of the form of a  b that means a is preferred to b. The transitive closure of Φ is denoted by Φc . The reflexive transitive binary relation w among answer sets of P r is defined as: X1 w X2 if there exist a ∈ X1 − X2 and b ∈ X2 − X1 where (a  b) ∈ Φc and there is not d ∈ X1 − X2 such that (b  d) ∈ Φc . X is called a preferred answer set if there is not an answer set Y such that Y A X. The following result states that any PLP can be encoded as a prioritized model expansion and presents the computational complexity of corresponding prioritized model expansion. A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 11 Theorem 2 A PLP Γ = (P r, Φ) can be expressed by a prioritized model expansion ΠI,ψ = (MXI,ψ , P ) where I represents P r, ψ characterizes the stable model se- mantics, and P is a preference expression representing Φc such that A is an optimal expansion of ΠI,ψ if and only if there is a preferred answer set M in Γ that can be constructed in polynomial time from A. Deciding the existence of an optimal expan- sion of ΠI,ψ that satisfies a goal φ and a preferred answer set of PLP satisfying φ are Σ2P -complete. Proof. Φ can be viewed as a preference expression in PMX and a program P r as a first order model expansion. According to [27], there is a correspondence between expan- sion structures of MXI , ψ and stable models of P r such that any stable model of P r can be one-to-one mapped in polynomial time to an answer set of P r and vice versa. Optimal expansions of ΠI,ψ are computed based on Element Dominance semantics that is the same as the notion of preferred answer sets in PLP. Also, since the compu- tational complexity of brave reasoning (i.e., the existence of an answer set that satisfies a conjunction of atoms) is NP-complete, based on Theorem 1, deciding if there is a preferred answer sets of Γ that satisfies φ is Σ2P -complete. Second, an ASO program [8] is a pair (Pg , R) where Pg is a generating logic program and R is a set of rules of the form r : C1 > ... > Ck ← a1 , ..., an , not b1 , ..., not bm . In each rule, ai and bi are literals. Also, Ci is a combination of atoms integrated through conjunction, disjunction, default negation (not) and strong negation (¬) that must ap- pear only before atoms. Ci > Cj ← body means that if body is satisfied, Ci is preferred to Cj . Given a set of l rules r1 , ..., rl , each answer set M of Pg is associated with a sat- isfaction vector d(M ) = hd1 (M ), ..., dl (M )i where di (M ) is called satisfaction degree of M in ri . Satisfaction degree denotes the minimum j of Cj s in ri that are satisfied by M . Preorder preference relation ≤ is defined over satisfaction degrees of a rule rk and two answer sets M1 and M2 as dk (M1 ) ≥ dk (M2 ) when q is the minimum i for all Ci s in M1 and s is the minimum j for all Cj s in M2 and q < s. Let M1 and M2 be two answer sets of Pg . M1 is preferred to M2 with respect to R (notation M1  M2 ) if for all i ≤ l, di (M1 ) ≥ di (M2 ). The relation between ASO and prioritized model expansion is formulated as follows. Theorem 3 Let ASO = (Pg , R) be an ASO program where Pg is disjunctive program and R is a set of preference rules. There is a prioritized model expansion ΠI,ψ = (MXI,ψ , P ) where ψ specifies the stable model semantics and I represents Pg such that each optimal expansion A of ΠI,ψ can be mapped in polynomial time to a preferred answer set of ASO. The problem of deciding if there is an optimal expansion of ΠI,ψ that satisfies a goal φ or there is a solution of ASO satisfying φ is Σ3P -complete. Proof. An ASO program can be translated into a PLP (P r∗ , Φ) where P r∗ is the union of Pg and a set of rules r1∗ and r2∗ where for each rule r ∈ R of the form C1 > C2 ← body(r), we have r1∗ : n1 ← C1 , body(r) and r2∗ : n2 ← C2 , body(r) and n2  n1 is in Φ. Therefore, based on Theorem 3, ASO can be converted into a prioritized model expansion. Since the existence of a an answer set that satisfies a set of ground atoms is Σ2P -complete ( i.e., brave reasoning in disjunctive logic programs with stable model semantics), deciding the existence of a solution of ASO that satisfies a goal formula φ is Σ3P -complete. 12 A. Ensan et al. Finally, our proposal can be also connected to a variety of other preference frameworks such as CP-nets [7] that model conditional preferences. A CP-net can be translated into an ASO (see [8]) and hence based on Theorem 4 can be encoded as a prioritized model expansion. Also, in the context of planning, preferences about temporal properties of plans can be converted into a logic program with preferences [34] and thus to a priori- tized model expansion (based on the result of Theorem 3). 5 Incomplete Preferences In this section, we focus on handling incomplete preference statements associated to search problems that are common in many practical cases. For example, assume that for buying a car, the customer believes that the red colour is not the best option and it is not the last choice either. In this example, some information is not known, that is to determine what colour is better or worse than red. Dealing with missing information is a broad field of study in database systems and declarative programming frameworks [19, 29]. The information incompleteness might be caused by updating databases [16], exchanging information [25], incomplete knowledge of the user about entire domain of interest, etc. The notion of an incomplete preference term is defined as follows. Definition 12 (Incomplete Preference Term) An incomplete preference term pinc inc x is a pair px = (dom(x) ∪ ⊥, ) where  is a preorder on dom(x) ∪ ⊥ and ⊥= {⊥1 , ..., ⊥m } is a set of nulls. An element ⊥j ∈⊥ represents a missing (or unknown) domain element in pinc x and e i ⊥j means that value e assigned to xi is preferred to something that is unknown or e is not the worst option to choose for xi . Likewise, ⊥j i e means that e is not the best value of xi . We define valuation v(pincx ) as a function v : dom(x) ∪ ⊥→ dom(x) that assigns elements in dom(x) to members of ⊥ appearing in pinc x such that v(e) = e for any e ∈ dom(x) and v(⊥i ) ∈ dom(x) for any ⊥i ∈⊥. A preference term px = (dom(x), ) can be viewed as a first order structure with vocabulary  and domain dom(x). An incomplete preference term corresponds to the well known notion of incomplete databases in which some fields value are null [29]. The completion of an incomplete preference term under closed world semantics is the set of all possible preference terms that are constructed by assignment of domain elements to nulls. Definition 13 The completion of an incomplete preference term pinc x under closed world inc semantics, notation  inc Jpx K , is defined as a set of preference terms as follows: Jpinc x K = v(px )|v is a valuation . Example 4 Assume vocabulary {car} with variables model, colour, and fuel that spec- ifies properties of a car. A car dealership has a set of cars that is equivalent to an inter- pretation of car. Let {Ford, Toyota, Honda} be the domain of model and {red, black, white, gray} be the domain of colour. Also, fuel can be gas, diesel, or electric. A set of preference terms are defined as follows. pm = (dom(m), m ) where m denotes the model and Honda m Toyota m Ford, and pc = (dom(c), c ) is an incomplete A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 13 preference term over possible colours of a car where ⊥1 c red that means that red is not the best colour. Also, pf = (dom(f ), f ) where gas f diesel and gas f electric indicating the favorite cars are those using gas instead of electric power or diesel. For a valuation v where v(⊥1 )=black, a black Honda with gas fuel is favoured to an electric red Ford. Model expansion task can be coupled with incomplete preference terms as follows. Definition 14 Incomplete prioritized model expansion is denoted by a pair ΠIincσ ,ψ = (MXIσ ,ψ , Pinc ) where MXIσ ,ψ is a model expansion and Pinc = {pinc inc x1 , ..., pxk } is a set of incomplete preference terms. The completion of an incomplete prioritized model expansion is defined as follows. Definition 15 The completion of ΠIincσ ,ψ = (MXIσ ,ψ , Pinc ) under closed world seman- tics (denoted by JΠIincσ ,ψ K) is a set of prioritized model expansions defined as JΠIincσ ,ψ K = (MXIσ ,ψ , JPinc K) where JPinc K = {Jpinc inc x1 K, ..., Jpxk K}. Structure A is called an optimal expansion of ΠIincσ ,ψ = (MXIσ ,ψ , Pinc ) if A is an optimal expansion of all Π 0 ∈ JΠIincσ ,ψ K. Determining if a given structure is an optimal expansion of an incomplete prioritized model expansion is defined as follows. Definition 16 ( Optimal Expansion of Incomplete PMX) Input: a τ -structure A with domain Dom and an incomplete prioritized model expansion ΠIincσ ,ψ = (MXIσ ,ψ , Pinc ) where τ = vocab(ψ) and Pinc = {pinc inc x1 , ..., pxk } is a set of incomplete preference terms, inc Question: Is A an optimal expansion of ΠIσ ,ψ ? Recall that one of the advantages of using model-theoretic semantics is to utilize model theory [10]. Here we employ some results of model theory including preservation theo- rems to study the computational complexity of Optimal Expansion of incomplete priori- tized model expansion. Preservation theorems show the relations between syntactic and semantic restrictions of first order formulas [30]. Results are not limited to first order logic and have been extended to first order logic with fixed point [2], Datalog [32], etc. We aim to show that the problem of dominant structure in the presence of incomplete preferences can be reduced to naive evaluation of a formula over an incomplete struc- ture and by using preservation properties of first order sentences and results in [20] to solve the problem of dominant structure with incomplete preferences in polynomial in the size of Dom. Before proceeding, we remind the formal definition of homomorphism and preservation of a formula. Assume A and B are two τ -structures. Let dom(A) and dom(B) be the domain of A and B. A function h : dom(A) → dom(B) such that for each R ∈ τ and for all (a1 , ...an ) (ai ∈ dom(A) for 1 ≤ i ≤ n), if (a1 , ...an ) ∈ RA , then (h(a1 ), ..., h(an ) ∈ RB ), is called a homomorphism from A to B. Let φ be a first- order sentence (all variables are bounded by a quantifier). We say that φ is preserved under homomorphism if for any structure A such that A |= φ, then for all structures B that there is a homomorphism h from A to B, B |= φ. Let ⊥= {⊥1 , ..., ⊥n } be a set of constants (nulls) and α be a vocabulary of symbols. An α-structure C with domain Dom ∪ ⊥ is called an incomplete structure. Each element of ⊥ is a null value that represents a missing domain value. Given a first order sentence φ 14 A. Ensan et al. and a structure C, the model checking task (query evaluation) is to decide whether C |= φ. Naive model checking, according to [29], treats null values as domain elements. It was discussed in [20] that evaluating queries directly on incomplete relational databases is equivalent to standard evaluation of queries if some syntactic restrictions are imposed to the query language. Theorem 4 Let model checking of ψ in MXIσ ,ψ be in the complexity class C. Solving the problem of Optimal Expansion of Incomplete prioritized model expansion is in co- NPC . Proof. In order to prove Theorem 4, it suffices to show that for two τ -structures A and B with domain Dom, A ≥Pinc B can be decided in polynomial time in the size of Dom and the rest is only to follow the steps taken in the proof of Proposition 2. To this end, we take the following steps. First, we construct an incomplete structure called preference structure as follows. Let pinc x1 = (dom(x1 ) ∪ ⊥, 1 ) be an incom- plete preference term. We construct the following incomplete α-structure C with do- main Dom0 = Dom ∪ ⊥ as follows. Consider vocabulary α = {p1 , SA , SB } and pC1 = {(a1 , a2 )|a1 , a2 ∈ Dom0 and a1 1 a2 }. Also, SA = RA . Define SB1 = RB and SB2 = {a|∃b ∈ SB1 ; a[x2 , ..., xn ] = b[x2 , ..., xn ]∧a[x1 ] ∈⊥}. Let define SB = SB1 ∪SB2 . Predicate p1 represents incomplete preferences among values of variable x1 , SA is the set of all tuples in RA , and S B is the set of all tuples in RB plus all tuples in B whose value of x1 is replaced by a null. Second, by slightly abuse of notation, valuation v(C) means valuation of any null value in C similar to the valuation of a preference term. Valuation v is a strong onto homo- morphism ( v is a surjective function) from C to C 0 where dom(C) = Dom ∪ ⊥ and dom(C 0 ) = Dom. The symbol JCK denotes the set of all C 0 where there is a valuation v (strong onto homomorphism) such that v(C) = C 0 . Any C 0 ∈ JCK is called a completion of C under closed world semantics. Third, according to Definition 4, Definition 10, and Definition 11, the task of deciding if B is preferred to A can be reduced to evaluation of whether C |= ∀x1 ∀x(SA (x1 , x)) → ∃y1 y(SB )(y1 , y) ∧ p1 (y1 , x1 )) where x = (x2 , ...xn ) and y = (y2 , ..., yn ). It was discussed in [20] that a positive first order formula ϕ (with no negation) with a guard of the form of ∀x(R(x) → ϕ), where R is a relation, is preserved under strong onto homomorphism. φ is a positive formula with a guard and completion of C under closed world semantics is equivalent to a set of structures to which there is a strong onto homomorphism from C. Thus, instead of evaluating all completions of C, we can naively evaluate φ. Since naive evaluation is in polynomial time in the size of Dom, evaluation of φ over all completions of C is polynomial in the size of Dom. Hence, deciding if B ≥pinc x1 A is polynomial in the size of Dom. For a set of incomplete preference terms Pinc = {pinc inc x1 , ..., pxk }, by induction on the number of incomplete preference terms, deciding B ≥Pinc A is polynomial in the size of Dom. The immediate result similar to Proposition 1 is that for a model expansion MXI,ψ with model checking of ψ in the complexity C, deciding if a given structure is a preferred expansion based on a set of incomplete preference terms is in co-NPC . The following result immediately follows from Theorem 4. Corollary 1 Let solving the decision version of model expansion MXIσ ,ψ be Σkp -complete. Solving the problem of Goal-Oriented Optimal Expansion with incomplete prioritized p model expansion is Σk+1 -complete. A Model-Theoretic View on Preferences in Declarative Specifications of Search Problems 15 6 Conclusion We proposed a novel language-independent preference framework and connected it to model expansion for characterizing preference-based computational decision and search problems. We demonstrated that adding preferences raises the computational complexity of deciding the existence of an expansion structure satisfying a goal. Addi- tionally, we introduced a new method to model incomplete preferences and used model theory results, namely preservation theorems, to find preferred expansions more effi- ciently. In future work, we will devise an algorithm that solves prioritized model ex- pansion using generic solvers empowered by propagators. The solver would provide symbolic explanations for rejecting and accepting models, and would follow a preferred computation path to prune the search space. References [1] Amgoud, L., Vesic, S.: Repairing preference-based argumentation frameworks. In: IJCAI. pp. 665–670. Citeseer (2009) [2] Atserias, A., Dawar, A., Kolaitis, P.G.: On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM (JACM) 53(2), 208–237 (2006) [3] Baier, J.A., McIlraith, S.A.: Planning with preferences. AI Magazine 29(4), 25–37 (2008) [4] Bhasker, J., Samad, T.: The clique-partitioning problem. Computers & Mathemat- ics with Applications 22(6), 1–11 (1991) [5] Bienvenu, M., Fritz, C., McIlraith, S.A.: Specifying and computing preferred plans. Artificial Intelligence 175(7-8), 1308–1345 (2011) [6] Bogaerts, B., Janhunen, T., Tasharrofi, S.: Stable-unstable semantics: beyond np with normal logic programs. Theory and Practice of Logic Programming 16(5-6), 570–586 (2016) [7] Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res.(JAIR) 21, 135–191 (2004) [8] Brewka, G., Niemelä, I., Truszczynski, M.: Answer set optimization. In: IJCAI. vol. 3, pp. 867–872 (2003) [9] Censor, Y.: Pareto optimality in multiobjective problems. Applied Mathematics and Optimization 4(1), 41–59 (1977) [10] Chang, C.C., Keisler, H.J.: Model theory, vol. 73. Elsevier (1990) [11] Codd, E.F.: Extending the database relational model to capture more meaning. ACM Transactions on Database Systems (TODS) 4(4), 397–434 (1979) [12] Delgrande, J., Schaub, T.: Expressing preferences in default logic. Artificial Intel- ligence 123(1), 41–87 (2000) [13] Delgrande, J., Schaub, T., Tompits, H.: Logic programs with compiled prefer- ences. arXiv preprint cs/0003028 (2000) [14] Dorndorf, U., Drexl, A., Nikulin, Y., Pesch, E.: Flight gate scheduling: State-of- the-art and recent developments. Omega 35(3), 326–334 (2007) [15] Eiter, T., Gottlob, G., Leone, N.: Abduction from logic programs: Semantics and complexity. Theoretical computer science 189(1-2), 129–177 (1997) 16 A. Ensan et al. [16] Elmasri, R., Navathe, S.: Fundamentals of database systems. Pearson (2015) [17] Ensan, A., Ternovska, E.: Modular systems with preferences. In: IJCAI. pp. 2940– 2947 (2015) [18] Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets (1974) [19] Gelfond, M.: Logic programming and reasoning with incomplete information. An- nals of mathematics and artificial intelligence 12(1), 89–116 (1994) [20] Gheerbrant, A., Libkin, L., Sirangelo, C.: Naive evaluation of queries over in- complete databases. ACM Transactions on Database Systems (TODS) 39(4), 31 (2014) [21] Gonzales, C., Perny, P., Dubus, J.P.: Decision making with multiple objectives using gai networks. Artificial Intelligence 175(7-8), 1153–1179 (2011) [22] Immerman, N.: Descriptive complexity. Graduate texts in computer sci- ence, Springer (1999). https://doi.org/10.1007/978-1-4612-0539-5, http:// dx.doi.org/10.1007/978-1-4612-0539-5 [23] Kießling, W.: Foundations of preferences in database systems. In: Proceedings of the 28th international conference on Very Large Data Bases. pp. 311–322. VLDB Endowment (2002) [24] Kolokolova, A., Liu, Y., Mitchell, D., Ternovska, E.: On the complexity of model expansion. In: Proc., 17th Int’l Conf. LPAR. pp. 447–458 (2010) [25] Libkin, L.: Data exchange and incomplete information. In: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. pp. 60–69. ACM (2006) [26] Mindolin, D., Chomicki, J.: Contracting preference relations for database applica- tions. Artificial Intelligence 175(7-8), 1092–1121 (2011) [27] Mitchell, D.G., Ternovska, E.: A framework for representing and solving np search problems. In: AAAI. pp. 430–435 (2005) [28] Pini, M.S., Rossi, F., Venable, K.B., Walsh, T.: Incompleteness and incomparabil- ity in preference aggregation: Complexity results. Artificial Intelligence 175(7-8), 1272–1289 (2011) [29] Reiter, R.: Towards a logical reconstruction of relational database theory. In: On conceptual modelling, pp. 191–238. Springer (1984) [30] Rosen, E., Weinstein, S.: Preservation theorems in finite model theory. In: Logic and computational complexity. pp. 480–502. Springer (1995) [31] Rossman, B.: Existential positive types and preservation under homomorphisms. In: Logic in Computer Science, 2005. LICS 2005. Proceedings. 20th Annual IEEE Symposium on. pp. 467–476. IEEE (2005) [32] Rudolph, S., Thomazo, M.: Expressivity of datalog variants–completing the pic- ture. In: 25th IICAI (2016) [33] Sakama, C., Inoue, K.: Prioritized logic programming and its application to com- monsense reasoning. Artificial Intelligence 123(1), 185–222 (2000) [34] Son, T.C., Pontelli, E.: Planning with preferences using logic programming. In: Logic Programming and Nonmonotonic Reasoning, pp. 247–260. Springer (2004) [35] Staworko, S., Chomicki, J., Marcinkowski, J.: Prioritized repairing and consistent query answering in relational databases. Annals of Mathematics and Artificial In- telligence 64(2-3), 209–246 (2012)