# localtoglobal_consistency_implies_tractability_of_abduction__eb6524c8.pdf

Local-to-Global Consistency Implies Tractability of Abduction

Michał Wrona Department of Computer and Information Science, Link oping University SE-581 83 Link oping, Sweden Email: michal.wrona@liu.se

Abduction is a form of nonmonotonic reasoning that looks for an explanation, built from a given set of hypotheses, for an observed manifestation according to some knowledge base. Following the concept behind the Schaefer s parametrization CSP(Γ) of the Constraint Satisfaction Problem (CSP), we study here the complexity of the abduction problem Abduction(Γ, HYP, M) parametrized by certain (ω-categorical) infinite relational structures Γ, HYP, and M from which a knowledge base, hypotheses and a manifestation are built, respectively. We say that Γ has local-to-global consistency if there is k such that establishing strong k-consistency on an instance of CSP(Γ) yields a globally consistent (whose every solution may be obtained straightforwardly from partial solutions) set of constraints. In this case CSP(Γ) is solvable in polynomial time. Our main contribution is an algorithm that under some natural conditions decides Abduction(Γ, HYP, M) in P when Γ has local-to-global consistency. As we show in the number of examples, our approach offers an opportunity to consider abduction in the context of spatial and temporal reasoning (qualitative calculi such as Allen s interval algebra or RCC-5) and that our procedure solves some related abduction problems in polynomial time.

Introduction Abduction is a form of logical inference that aims at finding explanations for observed manifestations, starting from some knowledge base. Abduction found many different applications in computer science and in artificial intelligence (Pople 1973), in particular to explanation-based diagnosis (e.g. medical diagnosis (Bylander et al. 1991)), text interpretation (Hobbs et al. 1993), and in planning (Herzig, Lang, and Marquis 2001). In this paper we study the complexity of abduction in the so-called Schaefer s framework originally used by Schaefer to study the CSP (Schaefer 1978). The CSP is a computational decision problem whose instance is a list of variables and a set of constraints each of which is imposed locally on some subset of the variables. The question is whether there is an assignment to variables that satisfies simultaneously all present constraints.

Copyright c 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

This problem is known to be NP-hard. Therefore, in order to look for easier subproblems, different parametrizations of the CSP are considered. The one we are interested in here is the problem CSP(Γ) parametrized by a relational ω-categorical structure, called also a constraint language, Γ which restricts the instances of the CSP to those set of constraints that can be built upon relations in Γ. In that framework one can express network satisfaction problems for many different qualitative calculi of crucial importance to spatial and temporal reasoning such as point algebra (Vilain, Kautz, and van Beek 1989), Allen s interval algebra (Allen 1983), left-linear point algebra (Duentsch 2005; Hirsch 1997) or RCC-5 (Duentsch 2005; Bennett 1994). In fact this approach, explained in details in (Bodirsky 2012), broadens the perspective and allows to obtain complexity results on constraint satisfaction in spatial and temporal reasoning not achievable before, e.g., (Bodirsky and K ara 2009; 2010; Bodirsky and Hils 2012).

Following this path, we study here the abduction problem Abduction(Γ, HYP, M) whose instance consists of three sets of constraints built upon relations in Γ, HYP, and M, respectively. The first one defines a knowledge base (KB), the second one offers a set of hypotheses (HYP) whereas the third one, a manifestation (M), consists of one constraint only. The question is whether there exists a subset H of HYP, called an explanation, consistent with the knowledge base such that the conjunction of KB and H entails M. When Γ, HYP, and M are over the two-element domain, then Abduction(Γ, HYP, M) may be seen as the verywell studied propositional abduction problem (Eiter and Gottlob 1995; Marquis 2000; Creignou and Zanuttini 2006; Nordh and Zanuttini 2008). In this paper, however, we are interested in the problem Abduction(Γ, HYP, M) where Γ, HYP, and M are ω-categorical structures. It offers the possibility to consider abduction in the context of spatial and temporal reasoning (Fisher, Gabbay, and Vila 2005; Renz and Nebel 2007; Duentsch 2005), in the context of qualitative calculi mentioned above. As related papers, we mention (Brusoni et al. 1998; Console, Terenziani, and Dupr e 2002; Brusoni et al. 1997) where temporal abduction based on point algebra, and Allen s interval algebra has been studied. All of this motivates the study of the complexity of abduction for ω-categorical structures, which was initiated in (Schmidt and Wrona 2013) and is continued in this paper.

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

To make things more concrete, we now present an example where Γ, HYP, and M are structures with first-order definitions in the ordered rationals, that is, in the structure (Q; <). In this case we can speak about abductive reasoning for events related by temporal point-based relations.

Example 1 Consider the following relational structures:

Γ := (Q; {(x, y, z) Q3 | (x > y x > z)}); HYP := (Q; {(x, y) Q2 | (x < y)}); M := (Q; {(x, y) Q2 | (x < y)}).

We look at an instance of Abduction(Γ, HYP, M) built upon variables V (which may be seen as events) and three sets of constraints: knowledge base (KB), e.g., (x > y x > z) (y > v y > w) that describes temporal dependencies between events in V using the relation in Γ; hypotheses (HYP) containing all constraints of the form (x < y) for all x, y VH where VH V ; manifestation (M) which is one constraint: (v < w) with v, w V . The question is whether there exists H HYP (a partial order on events in VH) such that constraints in KB H entails (v < w) (if constraints in KB H are satisfied, then the event v has to take place before the event w).

A primary algorithmic technique for solving CSP(Γ), is the process of establishing k-consistency (Mackworth 1977). According to the definitions in (Freuder 1982; Dechter 1992), the process of establishing k-consistency converts an instance P of the CSP into an instance P that has the same set of solutions as P and is k-consistent, that is, every partial solution to (k 1) variables may be extended to any other variable. An instance of the CSP with n variables is strongly k-consistent if it is i-consistent for any (i k) and is globally consistent if it is strongly n-consistent. It is very well known that for many constraint languages Γ there is k such that the problem CSP(Γ) can be solved by establishing (strong) k-consistency. In this case CSP(Γ) is solvable in polynomial time. Sometimes it is enough to obtain global consistency. We say that Γ has local-to-global consistency if there is k such that establishing strong kconsistency on every instance P of CSP(Γ) yields a globally consistent variant P of P. In this article we investigate a natural question of whether under any natural conditions the problem Abduction(Γ, HYP, M) can be solved by the algorithm based on establishing k-consistency. To answer this question affirmatively, we consider a natural restriction OE-ABD (Γ, M) of Abduction(Γ, HYP, M). Our main contribution is a procedure Lt G-OEAbd that solves the problem OE-ABD (Γ, M) in polynomial time when the expansion of Γ with complements of relations in M has local-to-global consistency. To show the strength of our algorithm, we investigate its applicability to temporal and spatial reasoning (point algebra, Allen s interval algebra, RCC-5). In particular we show that it solves OE-ABD (Γ, M) when Γ is a basic Ord-Horn language (Nebel and B urckert 1995; Chen and Wrona 2012;

Wrona 2012) and M that contains all binary relations definable in (Q; <). We also show that our procedure solves all tractable equality abduction problems studied in (Schmidt and Wrona 2013). We finally observe that there are structures Γ such that CSP(Γ) is solvable in P by establishing k-consistency for which OE-ABD (Γ, M) is NP-hard. As an example consider Γ = (N; {(x, y, z) N3 | (x = y x = z)}) and M = (N; =, =). It is easy to show that CSP(Γ) is solvable in P by establishing k-consistency (one can write an appropriate Datalog program, see (Bodirsky and Dalmau 2013)). On the other hand, it follows from (Schmidt and Wrona 2013) that OE-ABD (Γ, M) is NP-complete. In (Wrona 2012) it was proved that Γ does not have local-to-global consistency.

Constraint Languages under Consideration

We now provide a few definitions from model theory that are of concern in this paper. For a more comprehensive reading in this topic we refer the reader to (Hodges 1993). We consider here relational structures (always if it is not specified otherwise) over finite signatures denoted by Greek letters such as Γ, or . For the sake of simplicity, we use the same symbols to denote relations and their corresponding relational symbols. If it is not stated otherwise we denote the domain of the structure under consideration by D. A signature is denoted by τ or σ. For a structure Γ over τ and a relational symbol R τ we write Rτ to denote the relation in Γ corresponding to R. Let σ and τ be signatures with σ τ. When is a σ-structure and Γ is a τ-structure with the same domain such that R = RΓ for all R σ, then Γ is called an expansion of . By Γ we denote the expansion of Γ by relations in . If Γ is a relational structure over a finite signature τ, then we write arity(Γ) or arity(τ) to denote the largest arity of a relational symbol occurring in τ. For an n-ary relation R on D we write R to denote the relation Dn \ R and for a relational structure Γ the notation Γ indicates a structure obtained from Γ by replacing every R in Γ by R. We say that a relational structure Γ is first-order (fo-) definable in (is a first-order reduct of ) if Γ has the same domain as , and for every relation R of Γ there is a firstorder formula φ in the signature of such that φ holds exactly on those tuples that are contained in R. A primitivepositive (pp-) formula over is a first-order formula built exclusively from conjunction, existential quantifiers, atomic formulas over the signature of and equalities: (x = y). A structure Γ is pp-definable in if it is fo-definable by a pp-formula. We say that a countably infinite structure is ω-categorical if all countable models of its first-order theory are isomorphic. All the structures considered in this paper are countably infinite and ω-categorical. A relational structure Γ is homogeneous (Macpherson 2011) if every isomorphism between finite substructures may be extended to an automorphism of Γ. The set of automorphisms of a structure Γ is denoted by Aut(Γ). It is closed under composition and hence it can be

also viewed as the group of automorphisms of Γ. Let n be a natural number. An orbit of an n-tuple (a1, . . . , an), with elements in D, under Aut(Γ) is a set of the form Orb = {(α(a1), . . . , α(an)) Dn | α Aut(Γ)}. We say that Aut(Γ) is oligomorphic if there are only finitely many orbits of n-tuples under Aut(Γ) for every n N. We now present a classical result on ω-categoricity.

Theorem 2 (Engeler, Ryll-Nardzewski, Svenonius) For a countably infinite structure Γ with countable signature, the following are equivalent:

1. Γ is ω-categorical; 2. Aut(Γ) is oligomorphic.

Representation of Relations In this paper whenever we consider an instance of the CSP or the abduction problem we always assume that all involved relations have a first-order definition in some countably infinite ω-categorical structure . Since these structures are subject to computation a natural question of a finite representation of these relations arises. The solution to this problem is suggested by Theorem 2. Indeed, every n-ary relation R with a first-order definition in is the union of orbits of n-tuples under Aut( ). By Theorem 2, it follows that R is the union of the finite number of orbits under Aut( ). Thus R can be represented in the finite way by the set S of representatives of orbits under Aut( ) consisting of one representative for each orbit contained in R. In this case we say that S is a representation of R wrt. and that R is represented wrt. . See also an example below.

Example 3 A relation R = {(x, y, z) Q3 | (x < y < z) (x > y > z)} with a first-order definition in (Q; <) consists exactly of two orbits of triples under Aut(Q; <), namely: Orb1 = {(x, y, z) Q3 | (x < y < z)} and Orb2 = {(x, y, z) Q3 | (x > y > z)}. Now, since (0, 1, 2) Orb1 and (2, 1, 0) Orb2, it follows that the set S = {(0, 1, 2), (2, 1, 0)} is a representation of R wrt. (Q; <).

Abduction Problems The usual definition of the Constraint Satisfaction Problem (CSP) goes as follows.

Definition 4 An instance of the CSP is a triple P = (V, D, C) with

V = {v1, . . . , vn}, set of variables, for some n N, D, a non-empty set (domain), C, a set of constraints C1, . . . , Cm over V and D, where each Ci is a pair (si, Ri), with si, a tuple of variables from V of lenght mi, the scope of Ci, and Ri an mi-ary relation over D, called the constraint relation of Ci.

Given P the question is as follows.

Is there a solution to P, i.e., is there a function f : V D such that for each i m, the mi-tuple f(si) Ri?

For an instance P we write Sol(P) to denote the relation consisting of tuples (f(v1), . . . , f(vn)) such that f is a solution to P. Due to intractability of CSP, which is in general NP-hard, one considers the following parametrization of the problem.

Definition 5 Let Γ be a relational structure. Then CSP(Γ) is the restriction of the CSP from Definition 4 to instances where all constraints are built from relations in Γ.

In this paper we study the abduction problem where a knowledge base as well as a set of hypotheses are given by sets of constraints; and a manifestation is a single constraint. We look for an explanation, that is, a subset of hypotheses consistent with the knowledge base (Condition 1 in the definition below) which together with the knowledge base entails the manifestation (Condition 2). Now comes the formal definition. For a constraint C = (s, R), the notation C indicates (s, R).

Definition 6 An instance of the abduction problem is a tuple P = (V, VH, D, KB, Hyp, M) with

V = {v1, . . . , vn}, set of variables, for some n N, a subset VH of V upon which explanations are built, D, a non-empty set (domain), and two sets of constraints given as in Definition 4: KB over D and V , (knowledge base), Hyp over D and VH, (hypotheses), and a single constraint M over D and V , (manifestation).

Given P the question is whether there is an explanation for P, i.e., a set of constraints H Hyp such that: 1. CSP(V, D, KB H) is satisfiable, and 2. CSP(V, D, KB H M) is not satisfiable.

The abduction problem is in general ΣP 2 -hard. Thus, it makes sense to consider parametrizations of this problem. The most natural one is in our opinion the following.

Definition 7 We define Abduction(Γ, HYP, M) to be the restriction of the abduction problem from Definition 6 to instances such that KB is any set of constraints built upon relations in Γ and variables in V , Hyp is any set of constraints built upon relations in HYP and variables in VH, and M is a single constraint built upon a relation in M and variables in V .

In this paper we consider a more restrictive version of the abduction problem defined in the following.

Definition 8 Let be an ω-categorical and homogeneous relational structure over a finite signature. By Orb we denote the structure over the domain of having as relations all orbits of tuples under Aut( ) of arity at most arity( ).

Example 9 Let = (Q; <). Then arity( ) = 2 and Orb = (Q; Q, <, >, =), where the first occurrence of Q states for the domain of Orb and the second one for the trivial unary relation having as elements all rationals.

We now define the restriction of the problem Abduction(Γ, HYP, M) that we call OE-ABD (Γ, M) and which depends on three relational structures: , Γ, M over a finite signature such that is ω-categorical, homogeneous, and Γ and M are first-order reducts of . We will assume that all relations occurring in instances of OE-ABD (Γ, M) are represented wrt. . In the name of this problem OE stands for orbit explanation . Indeed, an explanation for an instance of OE-ABD (Γ, M) is built from constraints formed upon relations in Orb and variables in VH. In fact in every instance of OE-ABD (Γ, M) all such constraints are also available to build an explanation.

Definition 10 Let be homogeneous and ω-categorical structure and Γ, M be first-order reducts of . We define OE-ABD (Γ, M) to be the abduction problem from Definition 6, where in every instance P = (V, VH, D, KB, Hyp, M):

constraints KB and M are as in Definition 7, and Hyp is a set of constraints that for every l, every l-tuple s of variables in VH, and every l-ary relation R in Orb contains a constraint (s, R).

Without loss of generality we will always assume that VH = {v1, . . . , va} for some a n.

Recall that , Γ, and M are over finite signatures. We define the size of an instance P of OE-ABD (Γ, M) to be the number of constraints in KB.

Example 11 Let Rg = {(x, y, z) Q3 | (x = y z > x)} and Rl = {(x, y, z) Q3 | (x = y z < x)}. Consider an instance of the abduction problem P = (V, VH, D, KB, Hyp, M) where:

V = {v1, v2, v3, v4, v5}, VH = {v1, v2, v3}, D = Q, KB = {((v1, v2, v4), Rg), ((v1, v3, v5), Rl)}, Hyp = {(v1, Q), (v2, Q), (v3, Q), ((v1, v2), <), ((v1, v3), <), ((v2, v3), <), ((v1, v2), >), ((v1, v3), >), ((v2, v3), >), ((v1, v2), =), ((v1, v3), =), ((v2, v3), =)}, M = ((v4, v5), >).

It is easy to verify that H ={{(v1, v2), =}, {(v1, v3), =}} is an explanation for P. Observe that P may be also seen as an instance of OE-ABD (Γ, Orb) where = (Q; <) and Orb is as defined in Example 9. Observe also that if HYP contained any constraint less, then P would not be an instance of OE-ABD (Γ, Orb).

We now prove that using the relations in Orb we can ppdefine all orbits of n-tuples under Aut( ), for every n.

Proposition 12 Let and Orb be as in Definition 8, n be any natural number and (a1, . . . , an) a tuple over domain of . Then there is a set of constraints built over variables {v1, . . . , vn} and relations in Orb such that Sol(V, D, C) is equal to an orbit of (a1, . . . , an) under Aut( ).

Local-to-Global Consistency Recall the definition of a solution to an instance P of the CSP given in Definition 4. A partial solution to an instance P = (V, D, C) is a mapping h from a subset V of V to D such that for every constraint Ci = (si, Ri) there is an extension f : V D of h such that f(si) Ri. For P = (V, D, C) and V V , we write Part Sol(V , P) with V = {vi1, . . . , vil} such that i1 < < il to denote the relation consisting of all tuples (f(vi1), . . . , f(vil)) such that f : V D is a partial solution to P.

Definition 13 Let P = (V, D, C) be an instance of the CSP. We say that an instance P is k-consistent if for every partial solution h : V D to P with V V and |V | = (k 1), and v V \V there is a partial solution f : V {v} D to P extending h. An instance P = (V, D, C) of the CSP is strongly k-consistent if it is l-consistent for every l k and it is globally consistent if it is strongly |V |-consistent.

Let P = (V, D, C) be an instance of the CSP. We say that P = (V, D, C ) is a k-consistent, strongly k-consistent or globally consistent variant of P if P has the same set of solutions as P and is k-consistent, strongly k-consistent or globally consistent, respectively. In (Bodirsky and Dalmau 2013), it was proved that if Γ is ω-categorical and over a finite relational signature, then for every k there is a polynomial time algorithm that computes a strongly k-consistent variant of a given instance P of CSP(Γ).

Definition 14 We say that a relational structure Γ has localto-global consistency wrt. k if every strongly k-consistent variant P of every instance P of CSP(Γ) is also globally consistent. We say that Γ has local-to-global consistency if it has local-to-global consistency wrt. some k.

Local-to-Global consistency for ω-categorical structures has also two more known characterizations. One is in terms of so-called polymorphisms, see (Bodirsky and Dalmau 2013). The other one, more suitable for our purposes is stated in terms of decomposability.

Definition 15 We say that a constraint language Γ is kdecomposable if every primitive positive formula in Γ is equivalent to a conjunction of at most k-ary primitive positive formulas.

The following result follows from Corollary 3 in (Bodirsky and Dalmau 2013) and Theorem 19 in (Bodirsky and Chen 2007).

Theorem 16 Let Γ be an ω-categorical relational structure. Then Γ has local-to-global consistency wrt. k if and only if Γ is (k 1)-decomposable.

We now translate Theorem 16 to the language of constraints.

Proposition 17 Let Γ be an ω-categorical structure with local-to-global consistency wrt. k and P = ({v1, . . . , vn}, D, C) be an instance of CSP(Γ). Then t Sol(P) if and only if for every subset {vi1, . . . , vil} of V with l < k it holds that proj{i1,...,il}(t) Part Sol({vi1, . . . , vil}, P).

The above characterization of local-to-global consistency suggest the following representation, called the kdecomposition, of Sol(P) for an instance P of the CSP.

Definition 18 Let P = (V, D, C) with V = {v1, . . . , vn} be an instance of the CSP. Then the k-decomposition of Sol(P) is the instance P = (V, D, C ) of the CSP such that for every V V with |V | < k the set C contains a constraint of the form

((vi1, . . . , vil), Part Sol(V , P)),

where V = {vi1, . . . , vil}.

The k-decomposition of Sol(P) for an instance P of CSP(Γ) is of polynomial size and can be obtained in polynomial time wrt. size of P.

Proposition 19 Let be an ω-categorical structure and k a fixed natural number. Then there exists an algorithm that for an instance P of the CSP such that all involved relations have a first-order definition in computes the kdecomposition of Sol(P) in which all relations are represented wrt. . The algorithm works in time polynomial wrt. the size of P.

Algorithm This section is devoted to present our main tractability result which simply follows from Theorem 23 proved below.

Theorem 20 Let be an ω-categorical and homogeneous structure and Γ, M first-order reducts of such that ΓM has local-to-global consistency. Then OE-ABD (Γ, M) is decidable in polynomial time.

Let P = (V, VH, D, KB, Hyp, M) be an instance of OE-ABD (Γ, M). As we will show, the question of whether there is an explanation for P is equivalent to the question of whether there is a partial assignment ap : VH D that can be extended to a : V D so that a satisifies KB but cannot be extended to any a : V D that satifies KB M. This is exactly Condition (1) in Proposition 21. This proposition is inspired by Proposition 1 in (Zanuttini 2003) where a similar observation has been made in the case of propositional abduction. We refer to this condition as to Zanuttini s condition.

Proposition 21 Let be an ω-categorical and homogeneous structure and Γ, M be first-order reducts of . Let P = (V, VH, D, KB, Hyp, M) be an instance of OE-ABD (Γ, M). Let P proj KB = Part Sol(VH, (V, D, KB)) and P proj

M = Part Sol(VH, (V, D, KB M)). Then P OE-ABD (Γ, M) if and only if

P proj KB P proj

As an Algorithm 1, we present the procedure Lt G-OEAbd that solves the problem OE-ABD (Γ, M) from Theorem 20. The algorithm calls the following sub procedures. (k+1)-Decomp Alg (P) that for a given instance P of the CSP such that all involved relations have a firstorder definition in returns the (k + 1)-decomposition

of Sol(P) such that all relations in P are represented wrt. . By Proposition 19, we have that the procedure (k+1)-Decomp Alg exists and that we can assume that it works in polynomial time wrt. the size of P. Proj Constr(V , (V, D, C)) returns (V , D, C ) such that C is a subset of C containing all constraints whose scope is completely included in V . We will need the following auxiliary result.

Lemma 22 Let P = (V, D, C) be an instance of the CSP, P the k-decomposition of Sol(P), and VH = {v1, . . . , va} for some a n. Then Proj Constr(VH, P ) is the kdecomposition of Part Sol(VH, P ).

Algorithm 1: Algorithm Lt G-OEAbd

// - an ω-categorical homogeneous structure and // Γ, M - fo-reducts of such that ΓM has

local-to-global consistency wrt. k. Data: An instance P = (V, VH, D, KB, Hyp, M) of the problem OE-ABD (Γ, M). Result: True if there is an explanation for P, and False otherwise. // Computation of (k + 1)-decompositions

1 P kdec KB := (k+1)-Decomp Alg (V, D, KB);

2 P kdec proj KB := Proj Constr(VH, P kdec KB );

M := (k+1)-Decomp Alg (V, D, KB M);

4 P kdec proj

M := Proj Constr(VH, P kdec

M ); // Checking Zanuttini s condition

5 forall the {vi1, . . . , vil} VH with l k do

6 Let ((vi1, . . . , vil), R1) P kdec proj KB

7 and ((vi1, . . . , vil), R2) P kdec proj

8 if R1 R2 then

9 return True

12 return False

In a nutshell, the algorithm first stores in the variable P kdec KB in Line 1 the (k + 1)-decomposition of Sol((V, D, KB)). By Lemma 22, the variable P kdec proj KB in Line 2 stores the (k + 1)-decomposition of Part Sol(VH, (V, D, KB)). In the same way, we argue that P kdec proj

M in Line 4 stores the (k + 1)-decomposition of Part Sol(VH, (V, D, KB M)). By Proposition 21, it is now enough to argue that the loop checks Condition (1). On one hand, if for all {vi1, . . . , vil} VH with l k we have that R1 R2, then by Proposition 17, it follows that P proj KB P proj

M . On the other hand, if there is {vi1, . . . , vil} VH with l k and t in R1 but not in R2, then t can be extended to t (Part Sol(VH, (V, D, KB)) \ Part Sol(VH, (V, D, KB M))). Indeed, it follows since: (1) Sol(P kdec KB ) = Sol((V, D, KB)), (2) P kdec KB is strongly k-consistent, and (3) ΓM has local-to-global consistency wrt. k.

The polynomiality of the algorithm follows by the observations that calls to procedures (k+1)-Decomp Alg and Proj Constr works in polynomial time and that the loop is launched O(nk) times, each of which takes constant time.

Theorem 23 Let be an ω-categorical homogeneous structure and Γ, M be first-order reducts of such that ΓM has local to global consistency wrt. k. Then P = (V, VH, D, KB, Hyp, M) is a positive instance of OE-ABD (Γ, M) if and only if the algorithm Lt G-OEAbd returns True. The algorithm Lt G-OEAbd works in time polynomial wrt. the size of P.

Applicability of the Algorithm Lt G-OEAbd Temporal Point-Based Abduction We first apply our algorithm to temporal point-based abduction which may be seen as abduction in the context of point algebra. In this case, we fix = (Q; <), which is a very well-known ω-categorical and homogeneous structure. Recall from Example 9 that Orb = (Q; Q, <, >, =). We consider now the problem OE-ABD (Γ, M) where Γ is so-called ORD-Horn (OH) language (Nebel and B urckert 1995), a special kind of structure with a first-order definition in (Q; <) and M = (Q; <, >, , , =, =). We say that Γ is an OH language if every relation in Γ can be defined as a conjunction of clauses of one of the following forms: (1) ((x1 = y1 xk = yk) (x y)), (2) (x1 = y1 xk = yk), or (3) (x y), where {<, , =}. In Theorem 1 in (Wrona 2012) it was shown that an OH language Γ over a finite signature has local-to-global consistency if and only if Γ is basic OH that is every relation in Γ can be defined as a conjunction of clauses of one of the following forms: (1) ((x1 = x2 x1 = xk) (y1 = y2 y1 = yl) (x1 < y1)), (2) (x1 = y1 xk = yk), or (3) (x y), where {<, , =}. Since for every basic OH language Γ we have that ΓM is also basic OH, by Theorem 1 in (Wrona 2012) and Theorem 20 above we obtain the following non-trivial result on the complexity of temporal abduction.

Theorem 24 Let = (Q; <), Γ be any basic OH language, and M = (Q; <, >, , , =, =). Then OE-ABD (Γ, M) is decidable in polynomial time by algorithm Lt G-OEAbd.

Equality Abduction Problem To the very best of our knowledge, the only complete complexity classification of the problem OE-ABD (Γ, M) has been obtained in (Schmidt and Wrona 2013) for socalled equality languages Γ, that is, first-order reducts of (N; =) where N is the set of natural numbers. In this case = (N; =) and M = (N; =, =). Depending on Γ it was shown that the problem OE-ABD (Γ, M) is in P, it is NPcomplete, or ΣP 2 -complete. The algorithm for the polynomial case presented along with the classification is unfortunately somewhat barehanded and specialized to equality languages only. But this problem is in P when every relation in Γ can be defined as a conjunction of clauses of the form (x1 = y1 xk = yk), that is, when Γ is basic OH. By Theorem 11 in (Schmidt and

Wrona 2013) and Theorem 24 it follows that the polynomial case in the classification of the equality abduction problem may be handled by procedure Lt G-OEAbd.

Theorem 25 Let = (N; =), Γ be an equality language, and M = (N; =, =). Then, if Γ is basic OH, then OE-ABD (Γ, M) may be solved in P by the procedure Lt G-OEAbd. Otherwise, it is NP-hard.

Abduction and Allen s Interval Algebra

Allen s interval algebra is a formalism introduced for temporal reasoning in Artificial Intelligence (Allen 1983). Consider now a structure B whose domain I are the pairs (u, v) Q2 with (u < v) and relations are so-called basic relations of Allen s interval algebra: P, M, O, S, F, D, E whose names stands for precedes, meets, overlaps with, starts, finishes, is during, and equals and are defined in a natural way (Bodirsky 2012). For instance, P = {((a, b), (c, d)) | b < c} and M = {((a, b), (c, d)) | b = c}. Now the network satisfaction problem for Allen s interval algebra can be viewed as CSP(A) where A is a first-order reduct of B that contains all binary relations first-order definable in B. This problem and hence also OE-ABDB(A, A) is NP-hard. Consider now a pointizable fragment ΓPIA of Allen s interval algebra (van Beek and Cohen 1990) which consists of all binary relations over intervals that can be defined as a 4-ary relation over (Q; <) by conjunctions of atomic formulas of the form (x1 < x2), (x1 = x2), (x1 = x2) and (x1 x2). Observe that ΓPIA contains all relations in B. Theorem 40 in (Bodirsky and Chen 2009) shows that ΓPIA has local-toglobal consistency wrt. 5. By this result and Theorem 20 we have what follows.

Theorem 26 Let B and ΓPIA be as specified above. Then OE-ABDB(ΓPIA, ΓPIA) is decidable in polynomial time by the procedure Lt G-OEAbd.

Abduction in Spatial Reasoning

The last example considers spatial reasoning in the context of the very well known formalism RCC-5 which operates on sets and the following basic binary relations: DR, PO, PP, PPI, and EQ stands for disjointness, proper overlap, proper containment, its inverse and equality, respectively. It was shown in (Bodirsky and Chen 2009) that the constraint satisfaction problem involving all these five relations may be defined as CSP(B0) for certain ω-categorical and homogeneous structure B0. By Theorem 33 in that paper we have that a structure Γ which is an expansion of B0 by a finite number of relations each of which is definable as a conjunction of clauses of the form (x1 = y1 xk = yk) has local-to-global consistency. By Theorem 20, we obtain the following result.

Theorem 27 Let Γ be an expansion of B0 by a finite number of relations each of which is definable by a conjunction of disjunction of disequalities. Then the problem OE-ABD(Γ, B0) is decidable in polynomial time by the procedure Lt G-OEAbd.

Acknowledgements

The author is supported by the Swedish Research Council (VR) under grant 621-2012-3239.

Allen, J. F. 1983. Maintaining knowledge about temporal intervals. Communications of the ACM 26(11):832 843. Bennett, B. 1994. Spatial reasoning with propositional logics. In Proceedings of the International Conference on Knowledge Representation and Reasoning, 51 62. Morgan Kaufmann. Bodirsky, M., and Chen, H. 2007. Oligomorphic clones. Algebra Universalis 57(1):109 125. Bodirsky, M., and Chen, H. 2009. Qualitative temporal and spatial reasoning revisited. Journal of Logic and Computation 19(6):1359 1383. Bodirsky, M., and Dalmau, V. 2013. Datalog and constraint satisfaction with infinite templates. J. Comput. Syst. Sci. 79(1):79 100. Bodirsky, M., and Hils, M. 2012. Tractable set constraints. Journal of Artificial Intelligence Research 45:731 759. Bodirsky, M., and K ara, J. 2009. The complexity of temporal constraint satisfaction problems. Journal of the ACM 57(2). An extended abstract appeared in the proceedings of STOC 08. Bodirsky, M., and K ara, J. 2010. A fast algorithm and Datalog inexpressibility for temporal reasoning. ACM Transactions on Computational Logic 11(3). Bodirsky, M. 2012. Complexity classification in infinitedomain constraint satisfaction. Memoire d habilitation a diriger des recherches, Universit e Diderot Paris 7. Available at ar Xiv:1201.0856. Brusoni, V.; Console, L.; Terenziani, P.; and Pernici, B. 1997. Later: Managing temporal information efficiently. IEEE Expert 12(4):56 64. Brusoni, V.; Console, L.; Terenziani, P.; and Dupr e, D. T. 1998. A spectrum of definitions for temporal model-based diagnosis. Artif. Intell. 102(1):39 79. Bylander, T.; Allemang, D.; Tanner, M. C.; and Josephson, J. R. 1991. The computational complexity of abduction. Artif. Intell. 49(1-3):25 60. Chen, H., and Wrona, M. 2012. Guarded ord-horn: A tractable fragment of quantified constraint satisfaction. In TIME, 99 106. Console, L.; Terenziani, P.; and Dupr e, D. T. 2002. Local reasoning and knowledge compilation for efficient temporal abduction. IEEE Trans. Knowl. Data Eng. 14(6):1230 1248. Creignou, N., and Zanuttini, B. 2006. A complete classification of the complexity of propositional abduction. SIAM J. Comput. 36(1):207 229. Dechter, R. 1992. From local to global consistency. Artificial Intelligence 55(1):87 108.

Duentsch, I. 2005. Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review 23:315 357. Eiter, T., and Gottlob, G. 1995. The complexity of logicbased abduction. J. ACM 42(1):3 42. Fisher, M.; Gabbay, D.; and Vila, L., eds. 2005. Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier. Freuder, E. 1982. A sufficient condition for backtrack-free search. Journal of the ACM 29(1):24 32. Herzig, A.; Lang, J.; and Marquis, P. 2001. Planning as abduction. In IJCAI-01 Workshop on Planning under Uncertainty and Incomplete Information. Hirsch, R. 1997. Expressive power and complexity in algebraic logic. Journal of Logic and Computation 7(3):309 351. Hobbs, J. R.; Stickel, M. E.; Appelt, D. E.; and Martin, P. A. 1993. Interpretation as abduction. Artif. Intell. 63(1-2):69 142. Hodges, W. 1993. Model theory. Cambridge University Press. Mackworth, A. K. 1977. Consistency in networks of relations. AI 8:99 118. Macpherson, D. 2011. A survey of homogeneous structures. Discrete Mathematics 311(15):1599 1634. Marquis, P. 2000. Consequence finding algorithms. In Handbook of Defeasible Reasoning and Uncertainty Management Systems (DRUMS), Vol. 5, 41 145. Kluwer Academic. Nebel, B., and B urckert, H.-J. 1995. Reasoning about temporal relations: A maximal tractable subclass of Allen s interval algebra. Journal of the ACM 42(1):43 66. Nordh, G., and Zanuttini, B. 2008. What makes propositional abduction tractable. Artif. Intell. 172(10):1245 1284. Pople, H. E. 1973. On the mechanization of abductive logic. In IJCAI, 147 152. Renz, J., and Nebel, B. 2007. Qualitative spatial reasoning using constraint calculi. In Aiello, M.; Pratt-Hartmann, I.; and van Benthem, J., eds., Handbook of Spatial Logics. Springer Verlag, Berlin. 161 215. Schaefer, T. J. 1978. The complexity of satisfiability problems. In Proceedings of the Symposium on Theory of Computing (STOC), 216 226. Schmidt, J., and Wrona, M. 2013. The complexity of abduction for equality constraint languages. In CSL, 615 633. van Beek, P., and Cohen, R. 1990. Exact and approximate reasoning about temporal relations. Computational Intelligence 6:132 144. Vilain, M.; Kautz, H.; and van Beek, P. 1989. Constraint propagation algorithms for temporal reasoning: A revised report. Reading in Qualitative Reasoning about Physical Systems 373 381. Wrona, M. 2012. Syntactically characterizing local-toglobal consistency in ord-horn. In CP, 704 719. Zanuttini, B. 2003. New polynomial classes for logic-based abduction. J. Artif. Intell. Res. (JAIR) 19:1 10.