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. The uniformity of the modeltheoretic 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 related 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.
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 generates a multitude of acceptable results. For example, in the context of resource management, 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 problem instance) to a solution structure that satisfies a formula (problem specification). The 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 formalisms such as CP-nets [7]. They used Codd's relational algebra [11] to combine modules 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 Σ P k -complete (k th level in the polynomial hierarchy) model expansions. Third, we study the relations of some preferencebased frameworks with prioritized model expansion. We apply the computational complexity 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.
A τ -structure A = (A, R A 1 , ..., R A n ) is a tuple where τ = {R 1 , ..., R n } is a relational vocabulary that is a set of non-logical relation symbols R i with associated arity k i , A is a domain, and for any R i ∈ τ , R A i is called the interpretation of R i and R A i ⊆ A ki . 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 MX Iσ,ψ ) 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 MX Iσ,ψ . 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 AC 0 , MX is NP-complete, SAT is undecidable. The combined complexity of model expansion for first-order logic is NEXPTIME. A complexity analysis 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 generation, and if the input vocabulary is equal to the vocabulary of formula ψ, it is equivalent to model checking.
A variety of problems in AI such as the Airport Gate Scheduling problem can be reduced 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
A graph G = (V, E) is an instance structure with vocabulary σ = {E} and domain V that is the set of vertices. The model expansion MX G E ,ψ 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.
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 M L 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 P = Σ P 0 = Π P 0 = ∆ P 0 , Σ P k+1 = NP Σ P k , ∆ P k+1 = P ∆ P k , and Π P k+1 = coNP Σ P k for k > 0.
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.
Let us fix a domain Dom. Consider k first order variables x 1 , ..., x k over Dom, vocabulary τ , and k-ary R ∈ τ . A k-ary tuple a = (a 1 , ..., a k ) is an assignment to an ordered set of variables x = (x 1 , ..., x k ) such that for 1 ≤ i ≤ k, a i ∈ Dom. We use the symbol a[x i ] to denote value a i . R(a) is called a ground atom where a ∈ Dom k . 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 τ , P ) where S τ is the set of all ground atoms of vocabulary τ over domain Dom and P is a preorder on S τ . Example 2 Consider a graph G = (V, E) and three colours R, B, and G as in Example 1. Suppose P = (S τ , P ) where domain V = {v 1 , v 2 , ...v n } is a finite set of nodes, τ = {E, R, G, B}, and R(v 1 ) ≈ P R(v 2 ) P R(v 3 ) states that it is equally preferred to have v 1 and v 2 with red colour and either of which is strictly preferred to v 3 with red colour. Also, G(v 2 ) B(v 3 ) denotes that having v 2 with green colour is favoured to blue v 3 .
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 P among τ -structures with domain Dom as follows.
Definition 4 (Preference Relation on Structures) Given a preference expression P = (S τ , P ), 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 ∈ S B , R(a) P S(b).
-Upper Bound Dominance (UBD). A ≥ ubd P B iff for all S ∈ τ and for all b ∈ S B , for some R ∈ τ , there is a such that a ∈ R A and R(a) P S(b).
-Element Dominance (ED) A ≥ ed P B iff for some R, S ∈ τ , there is b ∈ S B and there is a ∈ R A such that R(a) P S(b) and there is not c for some T ∈ τ such that c ∈ T B and T (c) P R(a).
To build a one-to-one correspondence between our preference model and other preference 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 which a variety of optimization problems can be encoded. We discuss this generality in more details in section 4. The strict version of ≥ y P where y ∈ {wp, ubd, ed} is defined as A > y P B if A ≥ y P B and B ≥ y P A does not hold. A is dominant to B based on semantics y where y ∈ {wp, ubd, ed} when A > y P B. Also, we say A is dominant to B with notation A > P B when there is y ∈ { wp, ubd, ed} such that A > y P B. The problem of deciding if A is dominant is called Dominant Structure problem that is characterized as follows. Proof. As stated by Definition 4, at most, we compare all tuples in R A and R B 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
where m is the number of elements in τ .
We remark that the vocabulary τ is fixed and our discussion on computational complexity is focused on data complexity.
A prioritized model expansion (PMX) is the problem of finding the most preferred expansion structures with respect to preferences.
Input: a formula ψ, input vocabulary σ ⊆ vocab(ψ), a σ-structure I, and a preference expression P = (S τ , P ), Find structure A such that A is an expansion structure of MX Iσ,ψ and there is not an expansion structure B such that B > P A.
The problem of prioritized model expansion is denoted by Π Iσ,ψ = (MX Iσ,ψ , P ) where MX Iσ,ψ is a model expansion and P = (S τ , P ) 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. 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σ,ψ = (MX Iσ,ψ , P ) where τ = vocab(ψ) and P = (S τ , P ) is a preference expression, and a formula φ such that φ is of the form R 1 (a 1 ) ∧ ... ∧ R l (a l ) where R i ∈ τ and R i (a i ) 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σ,ψ = (MX Iσ,ψ , P ) be in the complexity class X. Solving the problem of Goal-Oriented Optimal Expansion is in NP X .
Proof. First, we non-deterministically guess a τ -structure A and in polynomial time check if a i ∈ R A i , 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 expansion 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 NP X .
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 MX Iσ,ψ 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 Σ P k can be encoded as MX Iσ,ψ where ψ is a formula of the form Q 1 , ..., Q k−1 ψ * such that for 1 ≤ i ≤ k, Q i is a second order quantifier where Q i = ∀ for k is odd and Q = ∃ otherwise, and ψ * is a first order formula. Therefore, when a decision version of a model expansion MX Iσ,ψ is in Σ P k , model checking of ψ is in Π P k−1 and based on Proposition 2, solving Optimal Expansion (MX Iσ,ψ , P ) is in Σ P k . The following result shows the impact of introducing preferences on Goal-Oriented Optimal Expansion for Σ P k -complete model expansions.
Theorem 1 Let the decision version of a model expansion be Σ P k -complete. The problem of Goal-Oriented Expansion Structure is Σ P k+1 -complete.
Proof. The membership to Σ P k+1 follows from the results of Proposition 2, Proposition 3, and properties of model expansion. Since the model expansion is in Σ P k , the complexity of model checking of ψ is in Π P k−1 . Therefore, based on proposition 2, the complexity of Optimal Expansion problem is in co-NP Σ P k−1 that is equal to Π P k . Also, based on Proposition 3, Goal-Oriented Optimal Expansion problem is in NP Π P k or NP Σ P k that is equal to Σ P k+1 . 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 Optimal Expansion similar to preferred logic programs [33]. An abductive logic program is defined as ALP = H, M, P 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 manifestation. 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 such that N ⊂ N . For a given hypothesis h ∈ H, deciding if there is a minimal solution N such that h ∈ N is Σ P 2 -complete. Second, consider an abductive logic program ALP = H, M, P . Let us define a logic program P as a set of rules of the form r : R(a) ← ¬S(b) for any R(a) P 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 . 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 (MX I,ψ , P ) where P * is translated into MX I,ψ based on [27]. Assume X 1 and X 2 are two stable models of P * . If X 1 is preferred to X 2 with respect to one of preference semantics in Definition 4, there is R(a) ∈ X 1 and S(b) ∈ X 2 such that R(a) P S(b). So, we have X 1 ∩ H ⊆ X 2 ∩ H and therefore, any preferred answer set is H minimal. Hence, finding a minimal solution of H, M, P 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 Σ P 2 -complete. Third, for model expansions in the higher levels of the polynomial hierarchy, consider the following. Σ P k -complete problems can be encoded as a combined logic program [6]. Π = (P g , P t ) is called a combined logic program where P g and P t 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 P g and there is not a stable model N of P t such that M ∩ G = N ∩ T . The decision version of this problem is Σ P 2 -complete. Recursively, the existence of a model of a combined program in depth 2 defined as Π 2 = (P g2 , (P g1 , P t )) is Σ P 3complete and similarly, in depth k, the existence of a model of (P
We introduce abductive combined program as C = H, M, Π where Π = (P g , P t ) is a combined logic program. W is a solution of C if there is a model S of (P g ∪ W, P t ) such that M ⊆ S. W is minimal if there is not a solution W such that W ⊂ W .
The problem of deciding if C = H, M, Π k for a given h ∈ H has a minimal solution containing h is Σ P 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 = {x 1 , ..., x m }, W = {w 1 , ..., w m }, X = {x 1 , ..., x m }, Y = {y 1 , ..., y n }, and Z = {z 1 , ..., z l } be a set of boolean variables in ϕ. Let t, h, and f be also boolean variables. Consider P g as a set of rules of the form {t ← x i , x i }, {w i ← x i }, {w i ← x i }, {t ← y 1 , ...y n , h}, and{f ← l 1 , ..., l r } where ¬(l 1 ∧, ..., ∧l r ) ∈ ϕ similar to [15]. For X ∪ X ⊆ H, a H-minimal solution of H, {t} ∪ W, P g does not contain f and it has either x i or x i . On the other hand, similar to [6], assume P t determines the truth value of a set of boolean variables Z. Also, for each clause C ∈ ϕ, suppose that P t 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 P t . 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 Σ P 3 -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 Σ P k -complete and hence the result follows.
Theorem 1 presents an important consequence of adding preferences to a Σ P k -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 preference relation between expansion structures derived from a preference expression can not be translated into axiomatization ψ in polynomial time unless P=NP or the polynomial hierarchy collapses.
Example 3 Consider the problem of graph colouring that was described as model expansion in Example 1. Let G = (V, E) be the input graph where
Assume that we prefer red colour for v 1 . Also, v 4 with red colour is favoured to v 5 with red colour and blue v 2 is preferred to green v 2 . These preference statements can be encoded by a preference expression P such that R(v 1 ) P B(v 1 ) and R(v 1 ) P G(v 1 ). Also, R(v 4 ) P R(v 5 ) and B(v 2 ) P G(v 2 ). The prioritized model expansion Π G,ψ = (MX G,ψ , P ) where MX G,ψ is the characterization of three-colouring for input graph G and P is the preference 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 R A = {v 1 , v 4 }, B A = {v 2 , v 5 }, and G A = {v 3 }.
In this subsection, we extend the notion of a preference expression by introducing preference 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 tuples (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.
A preference term p is a pair p = (A, ) where A is a set and is a preorder over A. Definition 11 (Preference Relation on Tuples) Given a set of preference terms P = {p x1 , ..., p x k } 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
A preference expression P can be constructed from a set of preference terms P such that for a predicate symbol R, R(a) P R(b) if and only if a P b. Prioritized model expansion then is extended to Π Iσ , ψ = (MX Iσ,ψ , P) where ≥ P is derived from a set of preference terms and the semantics of optimal expansion is exactly as before.
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 computational 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 among answer sets of P r is defined as:
X is called a preferred answer set if there is not an answer set Y such that Y 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.
Theorem 2 A PLP Γ = (P r, Φ) can be expressed by a prioritized model expansion Π I,ψ = (MX I,ψ , P ) where I represents P r, ψ characterizes the stable model semantics, 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 expansion of Π I,ψ that satisfies a goal φ and a preferred answer set of PLP satisfying φ are Σ P 2 -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 expansion structures of MX I , ψ 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 computational 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 Σ P 2 -complete. Second, an ASO program [8] is a pair (P g , R) where P g is a generating logic program and R is a set of rules of the form r :
In each rule, a i and b i are literals. Also, C i is a combination of atoms integrated through conjunction, disjunction, default negation (not) and strong negation (¬) that must appear only before atoms. C i > C j ← body means that if body is satisfied, C i is preferred to C j . Given a set of l rules r 1 , ..., r l , each answer set M of P g is associated with a satisfaction vector d(M ) = d 1 (M ), ..., d l (M ) where d i (M ) is called satisfaction degree of M in r i . Satisfaction degree denotes the minimum j of C j s in r i that are satisfied by M . Preorder preference relation ≤ is defined over satisfaction degrees of a rule r k and two answer sets M 1 and M 2 as d k (M 1 ) ≥ d k (M 2 ) when q is the minimum i for all C i s in M 1 and s is the minimum j for all C j s in M 2 and q < s. Let M 1 and M 2 be two answer sets of P g . M 1 is preferred to M 2 with respect to R (notation
. The relation between ASO and prioritized model expansion is formulated as follows.
Theorem 3 Let ASO = (P g , R) be an ASO program where P g is disjunctive program and R is a set of preference rules. There is a prioritized model expansion Π I,ψ = (MX I,ψ , P ) where ψ specifies the stable model semantics and I represents P g 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 Σ P 3 -complete. Proof. An ASO program can be translated into a PLP (P r * , Φ) where P r * is the union of P g and a set of rules r * 1 and r * 2 where for each rule r ∈ R of the form C 1 > C 2 ← body(r), we have r * 1 : n 1 ← C 1 , body(r) and r * 2 : n 2 ← C 2 , body(r) and n 2 n 1 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 Σ P 2 -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 Σ P 3 -complete.
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 prioritized model expansion (based on the result of Theorem 3).
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 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 p inc x is a pair p inc x = (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 p inc
x and e i ⊥ j means that value e assigned to x i is preferred to something that is unknown or e is not the worst option to choose for x i . Likewise, ⊥ j i e means that e is not the best value of x i . We define valuation v(p inc x ) as a function v : dom(x) ∪ ⊥→ dom(x) that assigns elements in dom(x) to members of ⊥ appearing in p inc
x such that v(e) = e for any e ∈ dom(x) and v(⊥ i ) ∈ dom(x) for any ⊥ i ∈⊥. A preference term p x = (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.
The completion of an incomplete preference term p inc
x under closed world semantics, notation p inc x , is defined as a set of preference terms as follows:
x )|v is a valuation .
Example 4 Assume vocabulary {car} with variables model, colour, and fuel that specifies properties of a car. A car dealership has a set of cars that is equivalent to an interpretation 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. p m = (dom(m), m ) where m denotes the model and Honda m Toyota m Ford, and p c = (dom(c), c ) is an incomplete preference term over possible colours of a car where ⊥ 1 c red that means that red is not the best colour. Also, p f = (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 terms as follows.
Definition 14 Incomplete prioritized model expansion is denoted by a pair Π inc Iσ,ψ = (MX Iσ,ψ , P inc ) where MX Iσ,ψ is a model expansion and P inc = {p inc x1 , ..., p inc x k } is a set of incomplete preference terms.
The completion of an incomplete prioritized model expansion is defined as follows.
Iσ,ψ = (MX Iσ,ψ , P inc ) under closed world semantics (denoted by Π inc Iσ,ψ ) is a set of prioritized model expansions defined as Π inc Iσ,ψ = (MX Iσ,ψ , P inc ) where P inc = { p inc x1 , ..., p inc x k }. Structure A is called an optimal expansion of Π inc Iσ,ψ = (MX Iσ,ψ , P inc ) if A is an optimal expansion of all Π ∈ Π inc Iσ,ψ . 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 Π inc Iσ,ψ = (MX Iσ,ψ , P inc ) where τ = vocab(ψ) and P inc = {p inc x1 , ..., p inc x k } is a set of incomplete preference terms, Question: Is A an optimal expansion of Π inc 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 theorems to study the computational complexity of Optimal Expansion of incomplete prioritized 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 structure 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 (a 1 , .. To this end, we take the following steps. First, we construct an incomplete structure called preference structure as follows. Let p inc x1 = (dom(x 1 ) ∪ ⊥, 1 ) be an incomplete preference term. We construct the following incomplete α-structure C with domain Dom = Dom ∪ ⊥ as follows. Consider vocabulary α = {p 1 , S A , S B } and p B is preferred to A can be reduced to evaluation of whether C |= ∀x 1 ∀x(S A (x 1 , x)) → ∃y 1 y(S B )(y 1 , y) ∧ p 1 (y 1 , x 1 )) where x = (x 2 , ...x n ) and y = (y 2 , ..., y n ). 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
A is polynomial in the size of Dom.
For a set of incomplete preference terms P inc = {p inc x1 , ..., p inc x k }, by induction on the number of incomplete preference terms, deciding B ≥ P inc A is polynomial in the size of Dom. The immediate result similar to Proposition 1 is that for a model expansion MX I,ψ 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-NP C . The following result immediately follows from Theorem 4. Corollary 1 Let solving the decision version of model expansion MX Iσ,ψ be Σ p k -complete. Solving the problem of Goal-Oriented Optimal Expansion with incomplete prioritized model expansion is Σ p k+1 -complete.
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. Additionally, we introduced a new method to model incomplete preferences and used model theory results, namely preservation theorems, to find preferred expansions more efficiently. In future work, we will devise an algorithm that solves prioritized model expansion 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.