Extensions of unification modulo ACUI

<jats:title>Abstract</jats:title><jats:p>The theory ACUI of an associative, commutative, and idempotent binary function symbol + with unit<jats:bold>0</jats:bold>was one of the first equational theories for which the complexity of testing solvability of unification problems was investigated in detail. In this paper, we investigate two extensions of ACUI. On one hand, we consider approximate ACUI-unification, where we use appropriate measures to express how close a substitution is to being a unifier. On the other hand, we extend ACUI-unification to ACUIG-unification, that is, unification in equational theories that are obtained from ACUI by adding a finite set<jats:italic>G</jats:italic>of ground identities. Finally, we combine the two extensions, that is, consider approximate ACUI-unification. For all cases we are able to determine the exact worst-case complexity of the unification problem.</jats:p>

section_content: An important topic in unification theory (Siekmann, 1989; Baader and Siekmann, 1994; Baader and Snyder, 2001) is investigating the complexity of deciding solvability of unification problems w. r. t. an equational theory E, that is, for a fixed equational theory E one considers as input a set of equations between terms of the form = {s 1 = ? t 1,. . ., s k = ? t k }, and asks whether there exists a substitution σ such that σ (s i ) = E σ (t i ) holds for i = 1,. . ., k. The complexity is then measured in the s of the unification problem. The theory ACUI of an associative, commutative, and idempotent binary function symbol + with unit 0 was one of the first equational theories for which the complexity of testing solvability of unification problems was investigated in detail (Kapur and Narendran, 1992). Interestingly, it turned out that this complexity depends on which symbols are allowed to occur in. In elementary E-unification, the terms in may only contain variables and the constant and function symbols occurring in E, that is, for E = ACUI these terms are built using variables and +, 0. In E-unification with constants, additional free constants (i. e., constants not occurring in E) may be used, whereas in general E-unification both free constants and free function symbols may occur in. Kapur and Narendran (1992) have shown that elementary ACUI-unification and ACUI-unification with constants are polynomial, whereas general ACUI-unification is NP-complete. 

Our renewed interest in ACUI-unification stems from the fact that the theory ACUI is a common subtheory of the equational theories corresponding to the Description Logics FL 0 (Baader, 1996) and EL (Baader et al., 1999) : for FL 0, ACUI is extended with unary function symbols that behave like homomorphisms and for EL the additional unary function symbols behave like monotone operators. In both cases, the binary symbol + corresponds to concept conjunction, and 0 to the top concept, which, in turn, are the description logic equivalents of "logical and" and "logical true". Unification with constants in (the equational theory corresponding to) FL 0 is known to be ExpTime-complete (Baader and Narendran, 2001) and NP-complete in (the equational theory corresponding to) EL (Baader and Morawska, 2009). We believe that ACUI is thus a good testing ground when trying to extend these results to more general settings. Here, we consider extensions of ACUI-unification in two orthogonal directions, which we then bring together: generalizing unification to approximate unification and adding a finite ground theory to ACUI. 

In approximate E-unification, one does not require that the left-and right-hand sides of the equations become equal modulo E, but only almost equal. The formal meaning of when a substitution approximately (i. e., "almost") solves a unification problem is formalized using distance measures between terms that are tailored towards the equational theory E in question. Approximate unification with constants in FL 0 was investigated in Baader et al. (2016) w. r. t. two such measures. In contrast to approaches that try to speed up reasoning by employing approximate inference techniques (Pan et al., 2016), this work (Baader et al., 2016) uses approximation as a way to extend the range of admissible solutions to a unification problem. In the present paper, we consider approximate unification with constants in ACUI w. r. t. three different measures: the first considers the number of equations that are violated, the second the number of constants violating at least one equation, and the third counts the overall number of violations (see Section 3 for exact definitions of these measures). It turns out that in the first and the third cases, the complexity increases from P to NP-complete when going from exact ACUI-unification with constants to the approximate case, whereas it stays in P for the second case. 

The results for unification in the Description Logics FL 0 and EL respectively shown in Baader and Narendran (2001) and Baader and Morawska (2009) are restricted to the case where equivalence of concept descriptions (corresponding to equality modulo the respective equational theories mentioned above) is considered without a background knowledge base. It is not known how to extend these decidability and complexity results to unification in the presence of so-called general TBoxes, though for EL there are some positive results for a restricted form of TBoxes (Baader et al., 2012). Since, from an equational theory point of view, general TBoxes correspond to finite sets of ground identities, we are interested in equational theories for which decidability of unification is stable under adding finite sets of ground identities. We will show in Section 4 that ACUI is such a theory. For the word problem, Marché proved in Marché (1996) that ACUI remains decidable if it is extended with a finite set of ground identities, but no complexity bounds are given. This result actually holds for a signature possibly containing several ACUI symbols and free function symbols. In Section 4 we consider a restricted setting where the ground theory G is built using only one ACUI symbol and free constants. In this case we can show that both the word problem and unification with constants remain solvable in P. Actually, the result for unification holds for unification problems with so-called constant restrictions, which allows us to employ the combination results from (Baader and Schulz, 1996) to show that general unification in ACUI ∪ G is NP-complete for any finite set of ground identities G satisfying the restrictions mentioned above. The complexity upper bounds shown in Section 4 (in P for unification with constant restrictions and in NP for general unification) are actually somewhat stronger: these upper bounds hold even if we view G to be part of the input, that is, measure the complexity in the size of and G. NP-hardness already holds for any fixed finite set of ground identities G. 

In the last part of this paper, we are combining the two extensions, that is, we consider approximate unification modulo ACUIG, that is, ACUI extended with a finite set of ground identities G. 

For the cases where one considers the number of violated equations or the overall number of violations, the NP-completeness results transfer from ACUI to ACUIG. For the remaining case where one considers the number of constants violating at least one equation, things become more interesting: we will show that there is a finite set of ground identities G such that approximate ACUIG-unification becomes NP-complete, but we will also exhibit a class of ground identities G for which this problem remains in P. 

In the following, we assume that the reader is familiar with the basic notions regarding equational theories and unification modulo equational theories, as they can be found, for example, in Baader and Nipkow (1998), Baader and Snyder (2001).
section_name: Introduction

section_content: In this section, we introduce the equational theory ACUI, characterize the word problem in ACUI using sets of constants, and recall the polynomial-time decision procedure for ACUI-unification by Kapur and Narendran (1992), which is based on a translation of ACUI-unification problems into propositional Horn formulae. This translation will then be extended in the next section to deal with approximate unification. 

Let = {+, 0} be the signature consisting of a binary function symbol + and a constant symbol 0. We denote the equational theory that states that + is an associative, commutative, and idempotent symbol with unit 0 by ACUI: ACUI := {(x + y) + z = x + (y + z), x + y = y + x, x + 0 = x, x + x = x}. 

Furthermore, let F be a countably infinite set of constants and V a countably infinite set of variables, where we assume that F, V, and are pairwise disjoint. We call the elements of F free constants since they are not constrained by the identities of ACUI. We denote the set of terms built from, F, and V as T (F, V), and the subset of ground terms, that is, terms in T (F, V) that do not contain variables, as T (F). For example, if a, b ∈ F and x, y ∈ V, then x + y and a + x belong to T (F, V), and a + b + b and b + a + a are elements of T (F). The latter two terms are actually equivalent modulo ACUI. More generally, two ground terms are equivalent modulo ACUI iff they contain the same free constants. To be more precise, given a ground term t ∈ T (F), we denote the set of free constants occurring in t with S(t). For example, S(a + b + b) = {a, b} = S(b + a + a), and S(a + 0) = {a} = S(a + a). The following result is well known. 

Lemma 2. 1. Let s, t ∈ T (F). Then s = ACUI t iff S(s) = S(t). 

Before we can define ACUI-unification, we need to introduce the notion of a substitution. A substitution is a mapping σ : V → T (F, V) that is the identity for all but finitely many variables. It can be homomorphically extended to a mapping from T (F, V) to T (F, V) in the obvious way, that is, σ (c) = c for every c ∈ F ∪ {0}, and
section_name: Unification Modulo ACUI

section_content: Input: A finite system = {s 1 = ? t 1,. . ., s k = ? t k } of equations between terms of T (F, V). 

Question: Is there a substitution σ such that σ (s i ) = ACUI σ (t i ) for every i = 1,. . ., k? Such a substitution is called an ACUI-unifier of. 

The ACUI-unification problems introduced in the above definition are called unification problems with constants since they may contain additional free constants (i. e., the elements of F, which do not belong to ), but no additional free function symbols of arity > 0. Now, let be such an ACUI-unification problem with constants and C and X be the finite sets of constants and variables respectively occurring in. In order to check whether has an ACUI-unifier or not, it is sufficient to consider substitutions that are the identity on V \ X and replace every x ∈ X by a term in T (C), that is, a ground term containing (in addition to 0) only constants from C. In fact, any ACUI-unifier of can be turned into one satisfying these properties by making it the identity on V \ X and replacing variables and constants in F \ C occurring in σ (x) for x ∈ X with 0. If we apply such a substitution σ to the terms occurring in, then we obtain terms in T (C). According to Lemma 2. 1, σ is an ACUI-unifier of iff S(σ (s)) = S(σ (t)) for every equation s = ? t ∈, that is, every constant c ∈ C occurring on the left-hand side σ (s) also occurs on the right-hand side σ (t) and vice versa. 

Example 2. 3. Consider the following ACUI-unification problem with constants:

We have C = {a, b, c} and X = {x 1, x 2, x 3 }. If we define σ (x 1 ) := a + c and σ (x 2 ) := b, then σ solves the first equation, since then all the constants in C occur on both sides. In order to solve the second equation as well, we then must define σ (x 3 ) such that a occurs in it, and c does not occur in it. This is satisfied by setting σ (x 3 ) := a, which then also satisfies the third equation. Note that setting σ (x 3 ) := a + b would have satisfied the second equation, but not the third. 

We will now recall Kapur and Narendran's (1992) reduction of solvability of ACUI-unification problems to satisfiability of propositional Horn formulae. Each equation in the unification problem is translated into several Horn clauses, and the overall Horn formula is the conjunction of all clauses for all equations. In this reduction, to which from now on we will refer to as the KNreduction, we use propositional variables p(a, x) for every a ∈ C and x ∈ X. The intuitive semantics of these variables is that p(a, x) is true iff a is not in S(σ (x)) for the given substitution σ. 

It is easy to see that each equation s = ? t ∈ can be written in the form

where s 0, t 0 ∈ T (F), m, n ≥ 0, x 1,. . ., x m ∈ X are distinct variables, and y 1,. . ., y n ∈ X are distinct variables. Now, for each equation of the form (1) and each a ∈ S(s 0 ) \ S(t 0 ), we generate the Horn clause p(a, y 1 ) ∧. . . ∧ p(a, y n ) → ⊥. 

Indeed, whenever an element a ∈ C is in S(s 0 ) but not in S(t 0 ), for the equation to hold true, a must occur in the image of some y j. The symmetric Horn clauses are also produced, that is, for each a ∈ S(t 0 ) \ S(s 0 )

Constants a ∈ S(s 0 ) ∩ S(t 0 ) are obviously harmless since they automatically occur on both sides of the equation. Thus, it remains to deal with the constants a ∈ C that are not in S(s 0 ) ∪ S(t 0 ). First, if such a constant a does not occur in the image of any of the variables on the right-hand side, then it should not occur in the image of any of the variables on the left-hand side, which is expressed by the Horn clauses

Again, we also need the symmetric clauses, that is, for each a ∈ C \ (S(s 0 ) ∪ S(t 0 )) we produce p(a, x 1 ) ∧. . . ∧ p(a, x m ) → p(a, y j ) f o r a l l j = 1,. . ., n. 

It is easy to see that the Horn formula obtained by conjoining all the Horn clauses derived from the unification problem is satisfiable iff has a solution (see Kapur and Narendran (1992) for details). The number of derived Horn clauses and their sizes are obviously polynomial in the size of the given ACUI-unification problem. Since satisfiability of propositional Horn formulae can be tested in linear time (Dowling and Gallier, 1984), this yields the following upper bound for deciding solvability of ACUI-unification problems with constants. 

Proposition 2. 4. (Kapur and Narendran, 1992). ACUI-unification with constants is decidable in polynomial time.
section_name: Definition 2.2. ACUI-unification problem with constants.

section_content: Intuitively, in approximate unification we consider the case where a given unification problem is not solvable, and we ask what is the "best we can do" towards solving it. De facto, we will also consider solvable unification problems as input for approximate unification, but then producing an exact unifier should be the best we can do. Before introducing formal approaches for how to rank the quality of approximate unifiers, we illustrate the underlying ideas using an example. 

Example 3. 1. Consider the following ACUI-unification problem with constants:

Trying to solve the first two equations already fully determines the substitution σ = {x 1 → 0, x 2 → a, x 3 → c}. Even though σ solves the first two equations, it does not solve the remaining two. Under σ, the set of free constants occurring in the left-hand side of the third equation becomes {a, b, c}, while the right-hand side yields the set {b, c}. Likewise for the fourth equation we obtain {a, b, c} on the left-hand side and {c} on the right-hand side. 

How far away is this substitution from being an exact solution? One idea is to count the number of equations that are not satisfied by it. In our example, this would yield the number 2 since σ does not solve the third and fourth equations. It is easy to see that, w. r. t. this measure, σ is actually the best we can do. In fact, in any solution of the fourth equation, b must occur in the image of x 1, and thus this substitution violates at least the first two equations. In addition, we have already seen that a solution of the first two equations cannot satisfy the third and fourth equations. Thus, it is not possible to satisfy more than two of the four equations. 

The above measure fails, however, to assess how far from being solved are the violated equations. Another possibility is to count how many of the elements of C take part in at least one violation, that is, occur on one side but not on the other when the substitution has been applied. In our example, there are two such constants, namely a and b. In fact, after applying σ, both a and b occur on the left-hand side of the fourth equation, but not on the right-hand side. In contrast, c does not take part in any violation. Again, it is not hard to show that this is the best we can do w. r. t. this measure. 

Still, this new measure ignores for how many equations a given element of C takes part in a violation. To take this aspect into account, we will also consider a measure that counts the overall number of violations, that is, sums up the number of equations each element of C violates. Returning to our example, this would be 3 violations for the substitution σ : 2 for a, 1 for b, and 0 for c. For this measure, we can actually do better than σ. In fact, if we define θ(x 1 ) := θ(x 2 ) := 0 and θ(x 3 ) := c, then a violates only the first equation, b violates only the fourth equation, and c violates no equation. Consequently, θ gets assigned the value 2, which is better than 3, which was the value for σ. 

In this example, and also in our general definitions, we consider only substitutions that are the identity on V \ X and assign terms in T (C) to the variables in X. The reason is that the assignment to variables in V \ X has no influence on the images of the left-and right-hand sides of equations in, and that free constants and variables in the images may only introduce additional violations, but cannot remove violations caused by constants in C. 

In the following, we will investigate all three of the measures sketched in the example, and determine the computational complexity of the corresponding decision problems, that is, given a unification problem and a natural number, is there a substitution whose value w. r. t. the given measure is ≤ ? It should be clear that these decision problems are in NP. Any substitution basically assigns subsets of C to the variables, and thus all such substitutions can be guessed in nondeterministic polynomial time. For a given substitution, the value assigned to it by the respective measure can obviously be computed in polynomial time. However, for the cases that are actually NP-complete, we also provide a reduction to Max-HSAT (Jaumard and Simeone, 1987), which is known to be NP-complete. This allows us to use existing optimized solvers for Max-HSAT (see e. g., (Marques-Silva et al., 2017) ) to solve approximate ACUI-unification problems. NP-hardness will be shown by a reduction from Max-HSAT. 

For later reference, we now define this problem formally.
section_name: Approximate Unification Modulo ACUI

section_content: Input: A nonnegative integer and a formula ϕ = n i=1 C i over a finite set of propositional variables P, where C i is a Horn clause, that is, of the form p 1 ∧ • • • ∧ p m → q, with p 1,. . ., p m being propositional variables, and q either a propositional variable or ⊥. Note that m = 0 is possible, where the empty conjunction is interpreted as. 

Question: Does there exist a set of indices I ⊆ {1,. . ., n} of cardinality at least, and a valuation v : P → {0, 1} such that v(C i ) = 1 for all i ∈ I. 

We call this decision problem Max-HSAT. For a given, Max-HSAT( ) consists of all Horn formulae ϕ = n i=1 C i for which there is a valuation that satisfies at least clauses C i.
section_name: Definition 3.2. (Max-HSAT).

section_content: As mentioned above, we consider only substitutions that are the identity on V \ X and assign terms in T (C) to the variables in X. We say that such a substitution σ violates an equation of the form (1) if

Definition 3. 3. (MinVEq-ACUI). Given an ACUI-unification problem with constants and a nonnegative integer, we now ask whether there exists a substitution σ such that at most of the equations of the system are violated by σ. We call this decision problem MinVEq-ACUI. For a given, MinVEq-ACUI ( ) consists of all ACUI-unification problems with constants for which there is a substitution that violates at most equations of the system. 

We will show that MinVEq-ACUI is NP-complete using reductions to and from Max-HSAT.
section_name: Minimizing the number of violated equations

section_content: For this purpose, we introduce new propositional variables good(i), whose rôle is to determine whether the ith equation is to be satisfied or not. We conjoin good(i) to the left-hand side of each of the Horn clauses derived from the ith equation, that is, if the ith equation is of the form (1), then we generate the following Horn clauses:

-For each a ∈ S(s 0 ) \ S(t 0 ): good(i) ∧ p(a, y 1 ) ∧. . . ∧ p(a, y n ) → ⊥; -For each a ∈ S(t 0 ) \ S(s 0 ): good(i) ∧ p(a, x 1 ) ∧. . . ∧ p(a, x m ) → ⊥; -For each a ∈ S(s 0 ) ∪ S(t 0 ): good(i) ∧ p(a, y 1 ) ∧. . . ∧ p(a, y n ) → p(a, x j ) for all j = 1,. . ., m; good(i) ∧ p(a, x 1 ) ∧. . . ∧ p(a, x m ) → p(a, y j ) for all j = 1,. . ., n. 

-Furthermore, we add the Horn clause → good(i). 

If k is the number of clauses generated by the original KN-reduction (see Section 2) and k is the number of equations in the unification problem, then we obtain k + k Horn clauses in this modified reduction. Let ϕ = C 1 ∧ • • • ∧ C k +k denote the Horn formula obtained by conjoining these Horn clauses. Before proving soundness and completeness of this modified reduction, we illustrate the above construction with an example. 

Example 3. 4. Consider the following ACUI-unification problem with constants, which is not solvable:

Then the modified reduction yields the following Horn clauses:

The system contains k = 3 equations and the original KN-reduction would produce k = 13 clauses. Thus, ϕ contains k + k = 16 Horn clauses. The valuation that sets p(a, x 1 ), p(a, x 2 ), p(a, x 3 ), p(c, x 3 ), and good(3) to false and all other variables to true satisfies all but the last clause. This corresponds to the substitution σ with σ (x 1 ) = σ (x 2 ) = a and σ (x 3 ) = a + c, which satisfies the first two equations and violates the third one. 

Intuitively, setting the propositional variable good(i) to false "switches off " the Horn clauses induced by the ith equation in the original KN-reduction. Consequently, the satisfaction of these clauses is no longer enforced, which means that the ith equation may be violated. By maximizing satisfaction of the clauses → good(i), we thus minimize the number of violated equations from. More precisely, we can show the following lemma. 

Lemma 3. 5. Let be an ACUI-unification problem with constants consisting of k equations and generating k clauses in the KN-reduction introduced in Section 2. Then we have, for all 0 ≤ ≤ k:

Proof. Let ∈ MinVEq-ACUI( ). This means that there exists a substitution σ such that at most of the equations in are violated by σ. We use σ to define a valuation of the propositional variables occurring in ϕ. For every a ∈ C and every variable x ∈ X we set p(a, x) to true iff a / ∈ S(σ (x)). In addition, we set good(i) to true iff σ does not violate the ith equation of. Now, suppose that the ith equation of is not violated by σ. Then our valuation makes all clauses corresponding to the ith equation evaluate to true, and in addition it also satisfies → good(i). If the jth equation of is violated, then good(j) is false. Consequently, all clauses of ϕ corresponding to the jth equation evaluate to true, but → good(j) evaluates to false. Summing up, the valuation induced by σ satisfies all the clauses of ϕ, with the exception of the clauses → good(j) if the jth equation is violated by σ. Since σ violates ≤ equations and there are k + k clauses in ϕ, the valuation satisfies

For the opposite direction, let ϕ ∈ Max-HSAT((k + k) -). This means that there is a valuation v and a set of indices

then all the clauses produced by the KN-reduction of Kapur and Narendran (see Section 2) for the ith equation evaluate to true. By the correctness of the KN-reduction, the ACUI-unification problem consisting of the equations for which v(good(i)) = 1 has a solution. Thus, there is a substitution that solves ≥ kequations of, that is, violates ≤ equations. This shows that ∈ MinVEq-ACUI( ). 

Since Max-HSAT is in NP, this lemma implies that MinVEq-ACUI also belongs to NP.
section_name: Reducing MinVEq-ACUI to Max-HSAT

section_content: Consider the Horn formula ϕ = C 1 ∧. . . ∧ C k, where C i is a Horn clause for i = 1,. . ., k. To construct a corresponding ACUI-unification problem with constants ϕ, it is sufficient to use a single free constant a, that is, we will have C = {a}. For every propositional variable p appearing in ϕ, we introduce a variable x p. Intuitively, a occurs in x p iff p is set to false. Now, each Horn clause in ϕ yields the following equations:

-

Obviously, this equation enforces that a cannot occur in x p if it does not occur in any of the variables

This equation enforces that a must occur in one of the variables x p i. 

-If C i is of the form → p, then the corresponding equation is

This equation ensures that a cannot occur in x p. 

The following example illustrates the construction of ϕ. 

Example 3. 6. Consider the Horn formula

The corresponding ACUI unification problem consists of the following equations:

It is easy to see that ϕ is not satisfiable. The valuation v that makes p 1 and p 2 true, and p 3 false satisfies all clauses except for the first one. Given the intuition that a occurs in x p i iff p i is set to false, this valuation induces the following substitution σ :

which solves all equations in the ACUI-unification problem except for the first one. 

More generally, we will show that there is a 1-1-relationship between valuations satisfying certain clauses and substitutions satisfying the corresponding equations. It is worth noting, however, that in Max-HSAT the number of satisfied clauses is maximized, whereas in MinVEq-ACUI the number of violated equations is minimized. 

Lemma 3. 7. Let ϕ = C 1 ∧. . . ∧ C k be a Horn formula and ϕ the corresponding ACUI unification problem. Then we have, for all 0 ≤ ≤ k:

Proof. Suppose that ϕ ∈ Max-HSAT( ). This means that there exists a valuation v and a set of indices I ⊆ {1,. . ., k}, |I| ≥ such that v(C i ) = 1 for every i ∈ I. Given such a valuation v, we define the substitution σ as follows:

We show that, for every i ∈ I, the ith equation is solved by this substitution. Indeed, if the ith equation is of the form:

This means that either v(p j ) = 0 for some j ∈ I or v(p) = 1. In the first case, a then occurs on both sides of the equation, and thus the equation is solved. In the second case, σ (x p ) = 0, and again the equation is solved by σ. 

This means that v(p j ) = 0 for some j ∈ I, and thus σ (x p j ) = a for some j ∈ I. Consequently, σ (x

is a sum of as and 0s, which implies that the ith equation is solved by σ. x p = ? 0, then C i = → p evaluates to true under v. This means that v(p) = 1, and thus σ (x p ) = 0. This shows that the ith equation is solved by σ. 

Consequently, the substitution σ solves at least equations of ϕ, and thus violates at most kequations, which implies ϕ ∈ MinVEq-ACUI(k -). 

For the opposite direction, if ϕ ∈ MinVEq-ACUI(k -), then there is a substitution σ such that at least equations of ϕ are not violated. We can assume without loss of generality that σ uses a as the only free constant. If we define v(p) = 0 iff a occurs in σ (x p ), then we can show (in the same way as above) that v satisfies at least clauses of ϕ, which implies ϕ ∈ Max-HSAT( ). 

Since Max-HSAT is NP-hard, this lemma implies that MinVEq-ACUI is also NP-hard. Put together, the two lemmas yield the exact complexity of MinVEq-ACUI. 

Theorem 3. 8. MinVEq-ACUI is NP-complete. The NP-hardness result holds even for ACUIunification problems with only one free constant.
section_name: Reducing Max-HSAT to MinVEq-ACUI

section_content: For the second measure, instead of minimizing the number of violated equations, we will minimize the number of violating elements of C, where as before C is the set of free constants occurring in the unification problem. 

Given a substitution σ, we say that a ∈ C violates an equation of the form (1)

where denotes the symmetric difference of two sets. We say that a ∈ C violates w. r. In contrast to the problem MinVEq-ACUI considered in the previous section, MinVEl-ACUI can be solved in polynomial time. In order to show this, we use projections of equations to free constants. As noted earlier, any term t ∈ T (F, V) can be written in the form t = t 0 + x 1 +. . . + x n, where t 0 ∈ T (F) is a ground term and x 1,. . ., x n are variables in V. Given a constant a ∈ F, the projection of such a term onto a is defined to be t a = π a (t 0 ) + x 1 +. . . + x n, where for a ground term t 0 ∈ T (F) we set π a (t 0 ) = a if a occurs in t 0, and 0 otherwise. Then the projection of an equation s = ? t to a is s a = ? t a, and the projection of an ACUI-unification problem with constants to a, denoted by a, is the system of the projections of the equations in to a. Finally, the projection of a ground substitution σ to a is the substitution σ a : V → T ({a}) defined as σ a (x) := σ (x) a. 

Consider the unification problem and the substitution σ introduced in Example 3. 4. The constant a violates w. r. t. σ, while b, c do not. For the elements of C = {a, b, c}, we obtain the following projections of :

Likewise, for the substitution σ we obtain the projections:

https://doi. org/10. 1017/S0960129519000185 Published online by Cambridge University Press

One can easily check that σ b and σ c solve b and c, respectively, whereas σ a does not solve a. This is closely related to the fact that a violates w. r. t. σ, but b and c do not. 

Lemma 3. 10. Let be an ACUI-unification problem with constants. Then the following holds:

(1) The constant a ∈ C violates w. r. t. σ iff σ a does not solve a. 

(2) Given substitutions σ a : V → T ({a}) for all a ∈ C, we define the substitution σ : V → T (C) as

Then we have σ a = σ a for all a ∈ C. 

(3) There is a substitution σ : V → T (C) such that at most of the elements of C violate w. r. t. 

σ iff at most of the ACUI-unification problems a (a ∈ C) are not solvable. 

Proof. We will show the first two facts stated in the lemma, and then use them to prove the third. 

(1) This is an easy consequence of the following equivalences. The constant a violates the equation s

(3) Suppose that there is a substitution σ : V → T (C) such that at most elements of C violate w. r. t. σ. Because of the first fact this implies that at least kof the projected unification problems a are solved by the projected substitutions σ a. Consequently, at most of the projected problems a are not solvable. For the opposite direction, suppose that at most of the systems a are not solvable. For every a ∈ C, if a is solvable, let σ a : V → T ({a}) be a substitution that solves it, and an arbitrary substitution V → T ({a}) otherwise. Define the substitution σ : V → T (C) as σ (x) := a∈C σ a (x) for all x ∈ V. Then the constant a ∈ C violates w. r. t. σ iff σ a = σ a solves a iff a is solvable. Consequently, at most of the elements of C violate w. r. t. σ. 

This completes the proof of the lemma. 

Due to the third fact stated in the above lemma, to check whether ∈ MinVEl-ACUI( ), it is sufficient to check which of the ACUI-unification problems a for a ∈ C are solvable. This can obviously be done in polynomial time. 

Theorem 3. 11. The problem MinVEl-ACUI is in P.
section_name: Minimizing the number of violating elements

section_content: A disadvantage of the violated elements measure used in the previous section is that it does not distinguish between constants that violate only one equation and those violating many equations. To overcome this problem, we count for each violating constant how many equations it actually violates. We say that a ∈ C violates p times w. r. t. σ if it violates p equations in w. r. t. σ. Further, we say that σ violates q times if q = a∈C p a where, for each a ∈ C, the element a violates p a times w. r. t. σ. Definition 3. 12. (MinV-ACUI). Given an ACUI-unification problem with constants and a nonnegative integer, we now ask whether there exists a substitution σ that violates at most times. We call this decision problem MinV-ACUI. For a given threshold value, MinV-ACUI ( ) consists of those ACUI-unification problems with constants for which there is a substitution that violates at most times. 

The approach used in Section 3. 1 to solve MinVEq-ACUI can easily be adapted to solve this new problem. Basically, we now introduce propositional variables good(i, a) (instead of simply good(i)) to characterize whether the element a ∈ C violates the ith equation. We conjoin good(i, a) to the left-hand side of each of the Horn clauses derived from the ith equation for a. Furthermore, we add the Horn clauses → good(i, a) instead of → good(i). Following the earlier notation, we obtain k + k|C| Horn clauses in this modified reduction, and again use ϕ to denote the Horn formula obtained this way. 

If we apply this modified reduction to the ACUI-unification problems of Example 3. 4, then we obtain the Horn clauses depicted in Figure 1. Consider the substitution θ with θ(x 1 ) = θ(x 2 ) = a and θ(x 3 ) = c. Then a violates the second and the third equations, whereas b and c do not violate any equation w. r. t. θ. We can use θ to define a valuation v, which sets p(a, x 1 ), p(a, x 2 ), p(c, x 3 ), good(2, a), good (3, a) to false and all other propositional variables to true. This valuation satisfies all clauses in Figure 1, except for → good(2, a) and → good (3, a). 

The following lemma states correctness of the modified reduction. Since its proof is very similar to the proof of Lemma 3. 5, we leave it to the reader.
section_name: Minimizing the number of violations

section_content: Horn formula obtained by applying the the modified reduction to. Then we have

Since Max-HSAT is in NP, this lemma implies that MinV-ACUI is also in NP. NP-hardness of MinV-ACUI actually follows directly from Lemma 3. 7. In fact, the reduction considered in this lemma requires only a single constant a. In this setting, counting the number of violated equations is the same as counting the number of all violations, and thus MinV-ACUI coincides with MinVEq-ACUI. This shows that MinV-ACUI is NP-hard. 

Theorem 3. 14. The problem MinV-ACUI is NP-complete.
section_name: Lemma 3.13. Let be an ACUI-unification problem consisting of k equations, and generating k clauses in the KN-reduction introduced in Section 2, and let C be the set of free constants occurring in . Denote with ϕ

section_content: In this section, we consider unification modulo ACUIG, that is, ACUI extended with a finite set of ground identities G. We will prove that, in this setting, we obtain the same complexity bounds as for ACUI-unification. Initially, we will demonstrate that the word problem in ACUIG is decidable in polynomial time. Subsequently, we will use this result to prove that ACUIG-unification with constant restrictions, a notion that generalizes unification with constants, is also decidable in polynomial time. Finally, using previous combination results from Baader and Schulz (1993) and the hardness result for general ACUI-unification by Kapur and Narendran (1992), we will conclude that general ACUIG-unification is NP-complete.
section_name: Unification Modulo ACUIG

section_content: Just as in Section 2, we consider the signature = {+, 0} and the equational theory ACUI that states that + is an associative, commutative, and idempotent binary function symbol with unit 0. But now we extend ACUI with a finite set of ground identities G ⊆ T (F) × T (F), and denote the equational theory obtained this way by ACUIG. The word problem for ACUIG asks whether two given terms s, t ∈ T (F) are equivalent modulo ACUIG, that is, whether s = ACUIG t holds or not. As already mentioned in the introduction, we can measure the complexity of this problem in two different ways. On one hand, we can assume that G is fixed beforehand, and then consider the word problem for the fixed equational theory ACUIG = ACUI ∪ G. The complexity of the word problem is then measured in the size of the input terms s, t. On the other hand, we can view G to be part of the input and then measure the complexity in the combined size of s, t, and G. If the complexity is measured in terms of s, t only, we will call this term complexity, and otherwise combined complexity. We will actually show that the word problem for ACUIG is in P for combined complexity, which obviously implies that it is also in P for term complexity. 

Recall that modulo ACUI, two ground terms s, t ∈ T (F) are equivalent iff they contain the same constants. However, in the presence of ground identities G, the latter condition is sufficient, but not necessary for two terms to be equivalent. In fact, ACUI ⊆ ACUIG obviously yields that S(s) = S(t) implies s = ACUIG t. However, the opposite direction need no longer hold, as shown by the following example. Consider the terms s = b + a + a and t = a + b + c, with corresponding sets S(s) = {a, b} and S(t) = {a, b, c}, and the ground theory G = {a + b = c}. We have

and thus s = ACUIG t, even though S(s) = S(t). Intuitively, the identity in G can be used to add c to the set {a, b}. 

We will now show how to decide whether two terms are equivalent modulo ACUIG. For this purpose, we saturate the sets of constants occurring in the terms using the identities in G to add constants, as we have done with c in our example.
section_name: The word problem for ACUIG

section_content: • begin with setting A G := A; • as long as there is an identity

This saturation process terminates after a number of iterations that is bounded by the cardinality of G. In fact, once an identity g i = h i is applied in the saturation process, it is no longer applicable since the set A G then contains S(g i ) ∪ S(h i ). It is also easy to see that the result of the saturation does not depend on the order in which rules are applied. Thus, each finite set A ⊆ F has a unique saturation A G, which can be computed in time polynomial in the cardinality of A and the size of G. c, d, e, f }. This is the final saturated set since it cannot be further extended using the identities in G. 

The following lemma is an easy consequence of the definition of saturation. 

Lemma 4. 3. Let A, B be finite subsets of F. Then the following holds: G. In particular, the combined and thus also the term complexity for the word problem for ACUIG is in P. Proof. Decidability in polynomial time obviously follows from the equivalence in the first statement since the saturation A G of a finite set A ⊆ F can be computed in polynomial time, and the cardinality of S(s), S(t) is bounded by the size of s, t. 

To show the equivalence, first assume that S(s) G = S(t) G. To conclude from this that s = ACUIG t, it is sufficient to show that saturation steps correspond to rewrite steps in ACUIG. Thus, assume that l ∈ T (F), and that g i = h i is an identity in G such that S(g i ) ⊆ S(l). Then l is of the form l = ACUI g i + l. We now have l = ACUI g i + l = ACUI g i + g i + l = G h i + g i + l = ACUI h i + l, and S(h i + l) = S(l) ∪ S(h i ). This shows that there are terms s G, t G ∈ T (F) such that u = ACUIG u G and S(u G ) = S(u) G for u ∈ {s, t}. By Lemma 2. 1, we thus know that S(s) G = S(t) G implies s G = ACUI t G, and thus we have s = ACUIG s G = ACUI t G = ACUIG t. 

Second, assume that S(s) G = S(t) G. To show that this implies s = ACUIG t, we construct a model A of ACUIG in which the identity s = t does not hold. As interpretation domain, we use all saturated sets over the constants occurring in s, t, or G, that is, := {A G | A ⊆ C}, where C consists of the elements of F that occur in s, t, or G. Since saturation adds only constants occurring in G, we know that A ⊆ C implies A G ⊆ C. The binary symbol + is interpreted as union followed by saturation, that is,

and c ∈ C as {c} G. Given a term u ∈ T (C), its interpretation in this algebra is S(u) G. This can easily be shown by induction on the structure of u, where the induction step uses the fact that

which is an easy consequence of Lemma 4. 3. Thus, S(s) G = S(t) G implies that the terms s, t have different interpretations in A. To show s = ACUIG t, it is thus sufficient to show that A satisfies all identities of ACUIG. For the identities in ACUI, this is an easy consequence of (2) and the fact that set union is associative, commutative, and idempotent and has ∅ as unit. Now consider an identity g i = h i ∈ G. When saturating the corresponding sets S(g i ) and S(h i ), one can in a first step go both from S(g i ) and from S(h i ) to S(g i ) ∪ S(h i ) (unless this step is void due to an inclusion). Saturating further, one thus obtains identical saturated sets, which shows that g i and h i are interpreted in A by the same saturated set.
section_name: Definition 4.1. Given a finite set of constants A ⊆ F, its saturation A G is obtained by iteratively applying the identities of G as follows:

section_name: Continuing

section_content: As in the previous subsection, let = {+, 0}, F a countably infinite set of constants, and V a countably infinite set of variables. Given a finite set of ground identities G ⊆ T (F) × T (F), we now consider unification modulo ACUIG = ACUI ∪ G. Note that in this setting the constants occurring in G are no longer free constants, but theory constants. Thus, an ACUIG-unification problem with constants may contain the constant 0, the constants from G, and additional free constants, that is, elements of F that do not occur in G. For a given unification problem, a constant restriction prohibits the occurrence of certain free constants in the image of certain variables. Definition 4. 5. ACUIG-unification problem with constant restriction. 

Input: A finite system = {s 1 = ? t 1,. . ., s k = ? t k } of equations between terms in T (V, F), a finite set of ground identities G = {g 1 = h 1,. . ., g m = h m } between terms in T (F), and a mapping r : D → 2 X where X ⊆ V is the set of variables occurring in and D ⊆ F is the set of free constants occurring in. 

Question: Is there a substitution σ such that σ (s i ) = ACUIG σ (t i ) for every i = 1,. . ., k and for every x ∈ X and d ∈ D we have that d does not occur in σ (x) if x ∈ r(d)? Such a substitution is called an ACUIG-unifier of w. r. t. r. 

Note that we consider the set of ground identities G to be part of the input. Thus, the complexity upper bound of P shown below for deciding ACUIG-unification with constant restriction holds for combined complexity, which implies the same upper bound also for term complexity. 

In the following, we assume that C ⊆ F is the set of constants occurring in or G, and X ⊆ V is the set of variables occurring in. As before, in order to check whether has a unifier w. r. t. r, it is sufficient to consider substitutions that are the identity on V \ X and replace every x ∈ X by a term in T (C). In fact, any ACUIG-unifier of w. r. t. r can be turned into one satisfying these properties by making it the identity on V \ X and replacing variables and constants in F \ C occurring in σ (x) for x ∈ X with 0. 

Intuitively, our algorithm for solving ACUIG-unification with constant restriction starts with a maximal substitution σ that respects the constant restriction. More precisely, maximal means that σ (x) contains all theory constants (constants occurring in G) and all free constants not disallowed by the constant restriction. Using the set notation, we have that S(σ

Note that this is an overapproximation of any solution θ (i. e., S(θ(x)) ⊆ S(σ (x)) holds for all variables x), if a solution exists at all. 

Next, whenever an equation s = ? t is not satisfied by the current substitution σ modulo ACUIG, we know that S(σ (s)) G = S(σ (t)) G. Assume for example that S(σ (s)) G ⊆ S(σ (t)) G. By Lemma 4. 3 we obtain that S(σ (s)) ⊆ S(σ (t)) G, that is, there occurs a constant a in σ (s) such that a / ∈ S(σ (t)) G. This constant is either introduced to σ (s) by the substitution, or it already occurs in s. In the latter case, since the substitution σ is an overapproximation of any solution, we cannot remedy this situation by adding the constant a to σ (t). Thus, the algorithm terminates in this case and returns Fail. Otherwise, there exists a variable x occurring in s such that S(σ (x)) ⊆ S(σ (t)) G. In this case, we trim the substitution, so that it no longer introduces this violation. This trimming process is such that the obtained substitution remains an overapproximation of any solution. The algorithm terminates successfully if all the equations are satisfied modulo ACUIG, in which case the current substitution σ is a solution. This happens after a polynomial number of steps since in each iteration of the while-loop the set S(σ (x)) for at least one variable x becomes smaller in the trimming step. Otherwise, the algorithm must terminate with failure at some point due to the reasons explained above. 

The formal description of our algorithm, called Algorithm 1, can be found in Figure 2. In this description, we use the following notation for turning a set of constants into the term that sums up these constants: given A ⊆ C, we denote with (A) the term a∈A a. Note that S( (A)) = A and (S(s)) = ACUI s for all s ∈ T (C). 

Before proving correctness of this algorithm, we illustrate how it works on two examples, one where the input is a solvable unification problem, and the other where the input problem is not solvable. 

Example 4. 6. Consider the system of equations
section_name: ACUIG-unification with constant restriction

section_content: Note that g is the only free constant occurring in, and thus it is the only constant occurring in this constant restriction. Also note that if we had x 1 ∈ r(g), then the second equation of would not be solvable. In addition, without G, this second equation would not be solvable either: b belongs to the left-hand side, but could never belong to the right-hand side without additional ground identities. 

The algorithm begins by setting

Next, the algorithm enters the while-loop and picks in each iteration an equation that is not satisfied modulo ACUIG:

-The second equation is not satisfied by σ modulo ACUIG: The algorithm then terminates since all equations are satisfied modulo ACUIG, and yields the substitution σ = {x 1 → c + e + g, x 2 → a + c + e} as output, which is indeed an ACUIG-unifier of that respects the constant restriction r. 

Next, we provide an instance that admits no solution, and demonstrate how the algorithm reaches this conclusion. 

Example 4. 7. Consider the system of equations

considered in the previous example, and the constant restriction

Note that g is the only free constant occurring in, and that r(g) = ∅ means that, in effect, there is no constant restriction, that is, all substitutions are admissible w. r. t. this constant restriction. 

The algorithm begins by setting Next, the algorithm enters the while-loop and picks in each iteration an equation that is not satisfied modulo ACUIG:

-The second equation is not satisfied by σ modulo ACUIG: It is not hard to see that the problem indeed does not have an ACUIG-unifier. Basically, the first equation implies that, for any unifier σ, a or d must occur in σ (x 1 ) since otherwise a cannot be produced on the right-hand side of the first equation. However, any such σ then violates the second equation. Proof. Termination in polynomial time is an easy consequence of the facts that (i) in each iteration of the while-loop, at least one constant is removed from the image of a variable, or the loop is exited; and (ii) saturation can be done in polynomial time. 

Since the algorithm only returns a substitution if the while-loop is exited regularly, this substitution satisfies all the equations of modulo ACUIG. It satisfies the constant restriction due to the fact that the original substitution satisfies it and that constants are only removed from, but never added to, the image of variables during the run of the algorithm. Consequently, if the algorithm returns a substitution, then this substitution is an ACUIG-unifier of w. r. t. r. This shows that the algorithm must return Fail in case has no unifier w. r. t. r. 

To prove the completeness of the algorithm, assume that σ is a ACUIG-unifier of w. r. t. r, and that the algorithm terminates during the rth iteration of the while-loop. Let σ (0) be the substitution σ before the first iteration of the while-loop. For i ∈ {1,. . ., r -1}, let σ (i) be the substitution obtained at the end of the ith iteration of the while-loop. 

We extend ⊆ to substitutions in a natural way by using point-wise comparison of constant sets, that is, τ ⊆ τ iff S(τ (x)) ⊆ S(τ (x)) for all x ∈ X. We prove by induction on i that σ ⊆ σ (i), for all i ∈ {0,. . ., r -1}. The base case i = 0 is obvious: since σ satisfies the constant restriction, we clearly have σ ⊆ σ (0). Let now i ∈ {0,. . ., r -2}, and assume that we already know that σ ⊆ σ (i). We must prove σ ⊆ σ (i+1). 

Since the algorithm does not exit the while-loop at this iteration, there is an equation s = ? t in that is not satisfied by σ (i) modulo ACUIG. In addition, since the algorithm does not fail at iteration i, there exists a variable x in s such that S(σ (x)) ⊆ S(σ (t)) G or y in t such that S(σ (y)) ⊆ S(σ (s)) G. Clearly, for every x ∈ X that does not appear in this equation, we have S( σ (x)) ⊆ S(σ (i) (x)) = S(σ (i+1) (x)). Let now x be a variable occurring in s (variables in t can be treated analogously). To prove that S( σ (x)) ⊆ S(σ (i+1) (x)), it suffices to prove that S( σ (x)) ⊆ S(σ (i) (x)) and that S( σ (x)) ⊆ S(σ (i) (t)) G. The first statement is true by the induction hypothesis. Now, we have

where (1) holds because x occurs in s, (2) by Lemma 4. 3, (3) because σ is a unifier of, and (4) by Lemma 4. 3 since σ ⊆ σ (i). This finishes the induction proof. Therefore, we now know that σ ⊆ σ (r-1). There are two possible reasons for the algorithm terminating in the rth iteration. Either the while-loop is exited regularly or the algorithm returns Fail. In the first case, σ (r-1) is a unifier and the algorithm returns this substitution. 

It remains to show that the second case cannot occur. In this case, we have that S(σ (r-1) (s)) G = S(σ (r-1) (t)) G for some equation s = ? t in, but S(σ (r-1) (x)) ⊆ S(σ (r-1) (t)) G for all variables x in s and S(σ (r-1) (y)) ⊆ S(σ (r-1) (s)) G for all variables y in t. This can only be the case if there is a constant c ∈ C such that c occurs in s, but c ∈ S(σ (r-1) (t)) G ; or c occurs in t, but c ∈ S(σ (r-1) (s)) G. We show that this is impossible. 

Thus assume that c occurs in s (the case where c occurs in t can be treated symmetrically). We have

where (1) holds since c occurs in s, (2) by Lemma 4. 3, (3) since σ is a unifier of, and (4) by Lemma 4. 3 since σ ⊆ σ (r-1). 

The following theorem is an immediate consequence of Proposition 4. 8. 

Theorem 4. 9. The combined complexity and thus also the term complexity of ACUIG-unification with constant restriction is in P. 

Note that this implies that elementary ACUIG-unification and ACUIG-unification with constants are also decidable in polynomial time. The next section deals with general ACUIG-unification.
section_name: , and the constant restriction

section_content: General ACUIG-unification problems differ from the ones we have considered until now in that the terms used in may contain free function symbols, that is, function symbols not occurring in the identities of ACUIG. For example, { f (x + a, a + b) = ? f (b + y, x)} is such a general ACUIGunification problem since it contains the additional function symbol f, which does not occur in the identities of ACUIG. Using techniques for the combination of unification algorithms, one can transfer complexity results for unification with constant restrictions to general unification. In fact, the following was proved by Baader and Schulz (1996) for arbitrary equational theories E, where linear constant restrictions are a special form of constant restrictions. 

Theorem 4. 10. (Baader and Schulz, 1996). If solvability of E-unification problems with linear constant restriction is in NP, then solvability of general E-unification problems is also in NP. 

Together with Theorem 4. 9 from the previous subsection, this provides us with an NPupper bound for general ACUIG-unification. The corresponding lower bound can be obtained by adapting the proof of NP-hardness for general ACUI-unification by Kapur and Narendran (1992). 

Theorem 4. 11. General ACUIG-unification is NP-complete, both w. r. t. combined complexity and w. r. t. term complexity. Proof. Membership in NP (for combined complexity, and thus also for term complexity) is an immediate consequence of Theorem 4. 9 together with Theorem 4. 10 since P ⊆ NP and any linear constant restriction is a constant restriction. 

We show that NP-hardness (w. r. t. term complexity) holds for any fixed finite set of ground identities G. This obviously implies NP-hardness also for combined complexity. This NP-hardness result can be shown by the same reduction from the set-matching problem used in (Kapur and Narendran, 1986) to show that general ACI-unification is NP-hard. To be more precise, this reduction yields ACI-unification problems of the form

where + is an associative, commutative, and idempotent function symbol, g is a unary free function symbol, and the terms s 1,. . ., s m, t 1,. . ., t n contain only free function symbols and variables. The presence of a unit and of ground identities in ACUIG does not change solvability of such problems compared to ACI since in the top-level sum the additional identities cannot be used due to the fact that all terms on this level start with the free function symbol g; even if the variables occurring in the terms g(s 1 ),. . ., g(s m ), g(t 1 ),. . ., g(t n ) are replaced by terms containing + and constant symbols from G (with the corresponding unifier being an ACUIG substitution, and not an ACI one), we can obtain an ACI unifier by abstracting away these "alien" subterms by free constants (see Lemma 4. 1 in (Baader and Schulz, 1996) and Example 4. 12 below). 

This shows that such a problem is solvable modulo ACI iff it is solvable modulo ACUIG for an arbitrary finite set of ground identities G, which completes our proof of NP-hardness of general ACUIG-unification w. r. t. term complexity. 

Example 4. 12. The above argument of abstracting away alien subterms, that is, subterms whose root symbol is from a different signature, is well known in unification theory. We illustrate it here using a simple example. Consider the general ACI-unification problem
section_name: General ACUIG-unification

section_content: In this section, we investigate how the addition of a ground theory to ACUI affects the complexity of approximate unification. Basically, we will investigate the same three measures that we treated in Section 3, but must adapt their definition to the extended setting. First, one needs to decide which are the constants that can lead to violations. In Section 3, these were the free constants occurring in the problem since presence or absence of the theory constant 0 cannot contribute to the violation of an equation. For example, given the equation x + a = ? a, the substitution σ = {x → 0} solves this equation, although syntactically, after applying this substitution, the left-hand side 0 + a contains 0 whereas the right-hand side a does not. This is the reason why we did not consider 0 when defining the set of constants S(t) contained in a term t. In contrast, constants occurring in G may lead to a violation. For instance, consider the equation from above and the ground theory G = {b + c = b}. The substitution θ = {x → b} does not solve the equation since θ(x + a) = b + a = ACUIG a = θ(a). Here, the constant b, which is a theory constant for ACUIG, violates the equation. This motivates to consider both the free constants occurring in and the theory constants different from 0 occurring in G when counting violations. However, when defining under what conditions such a constant violates an equation, one cannot just consider the constants explicitly occurring on the left-and the right-hand side after applying the substitution. In fact, if we consider the equation x + c = ? b, then the substitution θ from above solves this equation, although c occurs in θ(x

To see whether a theory constant from G really violates an equation, we first need to apply saturation to the sets of constants occurring on each side of the equation. 

In the following, let G be a ground theory, that is, a finite set of ground identities between terms of T (F), and = {s 1 = ? t 1,. . ., s k = ? t k } an ACUIG-unification problem with constants. We denote the set of constants appearing in or G with C and the set of variables appearing in with X. As before, it is sufficient to consider only substitutions that are the identity on V \ X and assign terms in T (C) to variables in X. 

Definition 5. 1. The substitution σ violates the equation s

and it violates modulo G w. r. t. σ if it violates at least one equation in modulo G w. r. t. σ. 

A constant a ∈ C violates modulo G p times w. r. t. σ if it violates p equations in modulo G w. r. t. σ. Finally, we say that σ violates q times modulo G if q = a∈C p a where, for each a ∈ C, the element a violates modulo G p a times w. r. t. σ. 

Given this redefined notions of violation, we can now formalize the three different decision problems for approximate ACUIG-unification analogously to how this was done in Section 3 for ACUI. 

Definition 5. 2. Let G be a ground theory, that is, a finite set of ground identities between terms of T (F). Given an ACUIG-unification problem with constants and a nonnegative integer, we ask whether there exists a substitution σ such that:

at most of the equations of the system are violated modulo G by σ. We call this decision problem MinVEq-ACUIG. at most constants violate modulo G w. r. t. σ. We call this decision problem MinVEl-ACUIG. 

-σ violates modulo G at most times. We call this decision problem MinV-ACUIG. 

It is easy to see that all three problems belong to NP w. r. t. combined complexity, and thus also w. r. t. term complexity. In fact, as mentioned before, we can restrict the attention to substitutions that assign terms in T (C) to the variables in X. Recall that, modulo ACUI, terms with the same constants are equivalent. Hence, for every x ∈ X, in order to define the assigned term σ (x) it suffices to determine the set of constants S(σ (x)) occurring in it. Consequently, any such substitution can be guessed in nondeterministic polynomial time. For a given substitution, the saturations of the constant sets on the left-and right-hand sides of the equations can be computed in polynomial time due to Proposition 4. 4, and thus the violations modulo G can be counted also in polynomial time. The only place where the ground theory plays a role in this straightforward NP-procedure is during the computation of the saturations. Since this computation is polynomial w. r. t. combined complexity, the NP upper bound also holds for combined complexity. 

Proposition 5. 3. The problems MinVEq-ACUIG, MinVEl-ACUIG, and MinV-ACUIG are in NP w. r. t. combined complexity, and thus also w. r. t. term complexity. In the next subsection, we will show that, for MinVEq-ACUIG and MinV-ACUIG, this NP upper bound is optimal, by showing NP-hardness w. r. t. term complexity for any fixed finite set of ground identities G. Note that the corresponding two problems are also NP-hard for ACUI, and actually MinVEq-ACUI and MinV-ACUI are used in the reduction that establishes these hardness results. 

Analyzing the complexity of MinVEl-ACUIG turns out to be more subtle. Recall that the corresponding problem is in P for ACUI. We will show that this upper bound in general does not transfer from ACUI to ACUIG. In fact, we will exhibit a fixed finite ground theory G for which the problem MinVEl-ACUIG is NP-hard w. r. t. term complexity. Obviously, this implies that MinVEl-ACUIG is NP-hard w. r. t. combined complexity. However, there are fixed finite ground theories G for which MinVEl-ACUIG is in P w. r. t. term complexity. An obvious example is G = ∅ since we know that MinVEl-ACUI is in P, but we will also give some other examples of such theories.
section_name: Approximate Unification Modulo ACUIG

section_content: We show NP-hardness of MinVEq-ACUIG and MinV-ACUIG by reduction from MinVEq-ACUI and MinV-ACUI, respectively. Lemma 5. 4. Let G be a finite ground theory. Then MinVEq-ACUIG and MinV-ACUIG are NP-hard w. r. t. term complexity. 

Proof. We restrict the attention to MinVEq-ACUIG (since MinV-ACUIG can be treated similarly), and reduce MinVEq-ACUI to MinVEq-ACUIG. Thus, let G be a fixed finite set of ground identities. Given an ACUI-unification problem, we can assume without loss of generality that contains none of the constants occurring in G (otherwise, we just rename the free constants in ). We now view as ACUIG-unification problem. 

To show correctness of the reduction, first assume that σ is a substitution that uses only constants occurring in, and which violates at most equations of. Equations s = ? t ∈ that are not violated satisfy σ (s) = ACUI σ (t), and thus also σ (s) = ACUIG σ (t). By Proposition 4. 4, this implies that these equations are also not violated modulo G by σ. Thus, if we view as ACUIG-unification problem, then σ violates at most equations of modulo G. 

Second, assume that σ is a substitution that uses only constants occurring in and G, and which violates at most equations of modulo G. Consider the substitution σ that is obtained from σ by replacing every constant from G by 0. We claim that all equations not violated modulo G by σ are not violated by σ. Thus, assume that s = ? t ∈ is an equation not violated by σ, which means that

( 3 )

To show that this implies S(σ (s)) = S(σ (t)), assume that c ∈ S(σ (s)). By our construction of σ and the fact that theory constants from G do not occur in, we know that c does not occur in G. In addition, c ∈ S(σ (s)) implies c ∈ S(σ (s)) G, and thus (3) yields c ∈ S(σ (t)) G. Since saturation w. r. t. G can only add theory constants from G, we obtain c ∈ S(σ (t)). Thus, c is contained in s or introduced by σ. The latter implies that c is also introduced by σ since only theory constants are removed when going from σ to σ. Thus, we have shown that S(σ (s)) ⊆ S(σ (t)). Since the other inclusion can be shown analogously, this shows that s = ? t is not violated by σ. Consequently, σ violates at most equations of. 

Together with Proposition 5. 3, this lemma yields the following complexity results. 

Theorem 5. 5. The problems MinVEq-ACUIG and MinV-ACUIG are NP-complete both w. r. t. term complexity and w. r. t. combined complexity.
section_name: The problems MinVEq-ACUIG and MinV-ACUIG

section_content: For the setting where the number of violating elements is minimized, the situation is less clear. Proposition 5. 3 yields an NP upper bound for combined complexity. However, since MinVEl-ACUI is in P, a reduction from it would not yield a matching NP lower bound for MinVEl-ACUIG. 

One could try to adapt the polynomial-time algorithm for MinVEl-ACUI to MinVEl-ACUIG. Recall that this algorithm is based on considering projections of the equations in to the free constants, and then solving the projected equations separately. While this would still work for the free constants in an ACUIG-unification problem, we now also need to consider the theory constants from G. For these, the separation into different equations does not work since the addition of constants by saturation would not be taken into account. This problem is illustrated in the next example. 

Example 5. 6. Consider the system of equations

and the set of ground identities

from Example 4. 7. As shown in that example, does not have an ACUIG-unifier. Thus, it makes sense to look for approximate unifiers. 

If we tried to solve the projected systems of equations (as described in Section 3. 2) independently for each constant modulo ACUIG, then we would see that 5 out of the 7 systems are not solvable: the systems for a, b, e, f, g are not solvable, whereas the ones for c, d are. This yields the substitution θ = {x 1 → c, x 2 → c}, w. r. t. which five constants violate (see the proof of Lemma 3. 10), and it also happens that only these five constants violate modulo G. 

However, by looking at the projections separately, we partially lose the possibility to prevent a violation by using G to add the violating constant to the side where it does not occur syntactically. For this, other constants than the violating one may need to be present. For instance, for the substitution {x 1 → c + e, x 2 → 0} the constant f is no longer violating (even though the projection of onto f is not solvable). Conversely, constants added by saturation may increase the number of violating constants, and their addition may depend on the presence of several constants. If, for instance, also included the trivially unsatisfiable equation f = ? 0, f would definitely be a violating element. Due to the second identity, the constants b, c, e would be violating as well. However, when projecting onto these constants, we would obtain the harmless equation 0 = ? 0. Returning to our original example, we can actually find a substitution w. r. t. which only two constants violate. If we set σ (x 1 ) := σ (x 2 ) := c + e, then the first equation is violated by a, and the second by g, while the third is not violated at all. Thus, w. r. As illustrated by this example, the approach used for MinVEl-ACUI to get a polynomial-time decision procedure in general does not work if we add ground identities. We will now show that, in fact, there is a fixed finite set of ground identities for which MinVEl-ACUIG is NP-hard w. r. t. term complexity. This obviously implies that the problem is also NP-hard for combined complexity. We will use a reduction from the NP-complete problem of 3-colorability (Garey and Johnson, 1990) to prove the hardness result.
section_name: The problem MinVEl-ACUIG

section_content: Given: A finite graph H = (X, E), where X is the set of vertices and E ⊆ X × X is the set of edges of H. Question: Does there exist a proper coloring of H with three colors (say a, b, c), that is, an assignment σ : X → {a, b, c} such that σ (x) = σ (y) for every (x, y) ∈ E?

The fixed ground theory G 3c employed to encode the "nature" of 3-colorability uses, as constants, the colors a, b, c and additionally e and f. Let C be the set of these five constants. The theory G 3c then consists of the following identities:

for every i, j ∈ {a, b, c}, i = j i + j + e = f. 

( 4 )

We will explain the intuition underlying these identities once we have introduced the ACUIG 3cunification problem. For the moment, just note that G 3c in fact does not depend on the input graph, that is, it is fixed in the sense that the same theory G 3c is used for every input graph. 

The input graph H = (X, E) is represented by the unification problem, where the vertices from X are used as variables. To be more precise, given an input graph H = (X, E), the corresponding ACUIG 3c -unification problem H consists of the following equations:

for every x ∈ X

x + e = ? 0,

( 5 )

for every (x, y) ∈ E

x + y + e = ? f,

finally, H also contains the equations

e = ? 0. 

At first sight, it may seem strange to have ground equations as part of a unification problem since they either hold modulo the given equational theory or are violated, independently of what substitution is used. However, in the context of MinVEl-ACUIG 3c, such equations can have a relevant effect. In fact, the equations ( 7 ) and ( 8 ) force all elements except f to be violating. Intuitively, the question is then whether we can keep f from being violating. If this is the case, then the identities of G 3c together with equation ( 5 ) ensure that every x ∈ X is assigned at most one of a, b, c. Furthermore, together with equation ( 6 ) the identities of G 3c ensure that x and y are assigned at least two different colors, if (x, y) ∈ E. Combining these two observations, we see that every variable (i. e., vertex) belonging to an edge is assigned a unique color, and that vertices that are connected by an edge are assigned different colors. 

Lemma 5. 8. The graph H = (X, E) has a proper coloring iff there is a substitution σ such that at most four constants violate the ACUIG 3c -unification problem H modulo G 3c w. r. t. σ. Proof. First, note that there is a substitution σ such that at most four constants violate the ACUIG 3c -unification problem H modulo G 3c w. r. t. σ iff the constant f does not violate H modulo G 3c. Now, assume that H = (X, E) has a proper coloring, that is an assignment σ : X → {a, b, c} such that σ (x) = σ (y) for every (x, y) ∈ E. Note that σ can also be viewed as a substitution. We claim that f does not violate H modulo G 3c w. r. t. this substitution. To see this, let us go through the equations of H :

-Equations of the form (5): such an equation x + e = ? 0 could only be violated by f modulo G 3c w. r. t. σ if an identity of the form (4) produced f on the left-hand side; this is not possible since σ (x) contains only one of the constants from {a, b, c} and not two different ones. -Equations of the form (6): for every (x, y) ∈ E, since σ (x), σ (y) ∈ {a, b, c} and σ (x) = σ (y), one of the identities (4) ensures that f does not violate the equation x + y + e = ? f modulo G 3c w. r. t. σ. f clearly does not violate the equations ( 7 ) and ( 8 ) modulo G 3c. 

Conversely, assume that σ : X → T (C) is a substitution such that f does not violate H modulo G 3c w. r. t. σ. Since, for every x ∈ X, f does not violate equation ( 5 ), we know that f does not appear in σ (x). Furthermore, σ (x) contains no more than one of a, b, c; otherwise, an identity of the form (4) would cause f to be violating. Moreover, since for every (x, y) ∈ E, f does not violate equation ( 6 ), we know that one of the identities (4) was activated, and hence σ (x) and σ (y) contain at least two different colors. Paired with the result for equations of the form (5), every variable belonging to an edge is assigned exactly one color. Overall, we can thus define the coloring τ by setting τ (x) to be the unique element of {a, b, c} that appears in σ (x) for vertices that belong to an edge, and arbitrarily set τ (x) for the remaining vertices. Furthermore, by the fact that f does not violate any equation of the form (6), we also obtain that τ is a proper coloring of H. This completes the proof of the lemma. 

This lemma shows that MinVEl-ACUIG 3c is NP-hard w. r. t. term complexity. Together with Proposition 5. 3, we thus obtain the following theorem. 

Theorem 5. 9. There exists a ground theory G 3c for which MinVEl-ACUIG 3c is NP-complete w. r. t. term complexity. This implies that MinVEl-ACUIG is NP-complete w. r. t. combined complexity. Note, however, that there are finite ground theories G for which MinVEl-ACUIG is in P w. r. t. term complexity. In fact, our results in Section 3. 2, in particular Theorem 3. 11, show that the empty ground theory G = ∅ is such a theory. 

Similarly, if we consider a theory G containing only identities of the form a = b for a, b ∈ C for a finite set of constants C, then MinVEl-ACUIG is in P w. r. t. term complexity. Basically, the idea is to reduce MinVEl-ACUIG to MinVEl-ACUI by replacing all occurrences of equivalent constants by a single representative of the class. In the resulting system of equations, there is no interaction between the different constants occurring in it, and hence it can be treated as a MinVEl-ACUI problem. An optimal substitution for this instance is also optimal for the original one, although the actual number of violating elements modulo G may be higher in the original problem. In fact, if b is the chosen representative of an equivalence class of constants, and b violates an equation in the MinVEl-ACUI instance, then all the elements of the class violate this equation modulo G. 

In order to provide less trivial examples of ground theories G for which MinVEl-ACUIG can be decided in polynomial time, we restrict the syntactic form of the ground identities that may occur in G. 

Definition 5. 10. The finite set of ground identities is called unary if every identity in G is of the form a = a + t for a constant a ∈ F ∪ {0} and a ground term t. 

Note that unary theories actually also cover the case of identities of the form a = b. In fact, it is easy to see that the theory G i = {a = b} is equivalent to the unary theory G u = {a = a + b, b = b + a} in the presence of ACUI:

The name "unary" for theories satisfying the above definition stems from the fact that, for such theories, the saturation rules are unary in the sense that their applicability depends on the presence of at most a single constant. Indeed, an identity of the form a = a + t induces a rule that is applicable whenever a ∈ F occurs in a given set of constants (or every time, if a = 0), and its effect is to add the constants occurring in t to this set (unless they are already there). 

Lemma 5. 11. Let G be a unary ground theory and s, t ∈ T (F). Then S(s + t) G = S(s) G ∪ S(t) G. In particular, this implies that S(s) G = a∈S(s) {a} G. 

Proof. The inclusion from right to left follows from Lemma 4. 3, and thus holds in general (i. e., also for non-unary theories):

To show the other direction, assume that a ∈ S(s + t) G. We show a ∈ S(s) G ∪ S(t) G by induction on the number of saturation steps needed to add a to S(s + t) G. In the base case, we have a ∈ S(s + t) = S(s) ∪ S(t) ⊆ S(s) G ∪ S(t) G. Thus, assume that a is added in step n of the saturation process, and that all the constants that have been added previously are contained in S(s) G ∪ S(t) G. By definition of saturation, there is a constant b ∈ F ∪ {0} and an identity b = b + u ∈ G with a ∈ S(u). If b = 0, then clearly a ∈ S(s) G (and also a ∈ S(t) G ), since S(s) G (S(t) G ) is saturated. Otherwise, if b ∈ F, it holds that b ∈ S(s) G ∪ S(t) G by the induction hypothesis. If b ∈ S(s) G, then the existence of the identity b = b + u in G and the fact that S(s) G is saturated imply that a ∈ S(s) G. In the same way, b ∈ S(t) G implies that a ∈ S(t) G. 

Note that this lemma need not hold for non-unary ground theories. An easy counterexample is G = {a + b = c}, where c ∈ S(a + b) G, but c ∈ S(a) G ∪ S(b) G. Also note that the theory G 3c used in the proof of Theorem 5. 9 does not satisfy this property. In fact, we have S(a

Given a unary ground theory G, we will show that MinVEl-ACUIG can be reduced to MinVEl-ACUI. Before we can describe this reduction, we need to extend the notion of saturation from sets of constants to terms, substitutions, and unification problems. Given a ground term s ∈ T (F), its saturation is s G := (S(s) G ). Note that we have S(s G ) = S(s) G for any s ∈ T (F), and that Lemma 5. 11 yields (s 1 +. . . 

For a ground substitution σ : X → T (F), we define its saturation σ G as σ G (x) := σ (x) G for every x ∈ X. Recall that a term t ∈ T (F, V) can be written in the form t = t 0 + x 1 +. . . + x n, where t 0 ∈ T (F) and x 1,. . ., x n ∈ V. We set t

Finally, given an ACUIGunification problem with constants, its saturation G consists of the equations s G = ? t G for every s = ? t in. 

The following lemma is an easy consequence of Lemma 5. 11. 

Lemma 5. 12. Let G be a unary ground theory, t ∈ T (F), and σ a ground substitution. Then

Proof. Let t be of the form t = t 0 + x 1 + • • • + x n for a ground term t 0. Then we have

The idea is now to reduce MinVEl-ACUIG for to MinVEl-ACUI for G. The following theorem states correctness of this reduction. Theorem 5. 13. Let G be a unary ground theory, an ACUIG-unification problem, and ≥ 0. Then the following are equivalent:

(1) There is a substitution σ such that at most constants violate modulo G w. r. t. σ. 

(2) There is a substitution θ such that at most constants violate G w. r. t. θ. 

Proof. Assume initially that there exists a substitution σ w. r. t. which has at most violating elements modulo G. It is easy to see that σ G is a substitution w. r. t. which G has at most violating elements. In fact, Lemma 5. 12 yields for every s

and hence G (viewed as a MinVEl-ACUI instance) has at most violating constants w. r. t. σ G. 

For the opposite direction, assume that there exists a substitution θ w. r. t. which G has at most violating elements (not considering G). Recall that, in Lemma 3. 10. 3, when constructing an optimal substitution for a MinVEl-ACUI problem, we only use non-violating elements. Hence, we can assume without loss of generality that θ introduces no violating constants. Under this assumption, we will now show that, also modulo G, has at most violating elements w. r. t. θ. Indeed, assume that a does not violate G w. r. t. θ. Then, for every s = ? t ∈ we have that a / ∈ S(θ(s G )) S(θ(t G )). 

-If a ∈ S(θ(s G )) ∩ S(θ(t G )), we obtain by Lemma 5. 12 that a ∈ S(θ(s)) G ∩ S(θ(t)) G, and hence a does not violate s

)), it is still possible that a ∈ S(θ(x) G ) for some x occurring in s (the case where x occurs in t is treated similarly), and hence a ∈ S(θ(s)) G. By Lemma 5. 11, we obtain that there exists some b ∈ S(θ(x)) such that a ∈ {b} G. Since we assume without loss of generality that θ does not introduce any violating elements, b is also not violating. Hence, b occurs in θ(t G ), and thus also in θ(t) G, which again by Lemma 5. 11 implies that a ∈ S(θ(t)) G. If, on the other hand, a / ∈ S(θ(x)) G for all variables x occurring in s or t, then we have a / ∈ S(θ G (s G )) ∪ S(θ G (t G )), which by Lemma 5. 12 is the same as a / ∈ S(θ(s)) G ∪ S(θ(t)) G. 

In any case, we conclude that a / ∈ S(θ(s)) G S(θ(t)) G, and hence a does not violate s = ? t modulo G. To sum up, we have shown that every non-violating element of G w. r. t. θ remains non-violating modulo G for w. r. t. θ, and thus the upper bound of for violating elements also holds in modulo G. 

Since saturation can be done in polynomial time (even if G is seen as part of the input) and MinVEl-ACUI can be solved in polynomial time, this theorem yields the following complexity result for the class of unary ground theories. 

Corollary 5. 14. Restricted to unary ground theories G, MinVEl-ACUIG is in P w. r. t. combined complexity, and thus also w. r. t. term complexity. Obviously, all we need for Theorem 5. 13 to hold is that the property stated in Lemma 5. 11 holds for G. Let us call such a theory "well behaved. " Definition 5. 15. The ground theory G is called well behaved if S(s + t) G = S(s) G ∪ S(t) G holds for all terms s, t ∈ T (F). By Lemma 5. 11, every unary theory is well behaved. From a syntactic point of view, the converse need not be true. However, semantically it is true: every well-behaved theory G is equivalent to a unary theory G, where G and G are equivalent if = ACUIG = = ACUIG. Lemma 5. 16. A ground theory is well behaved iff it is equivalent to a unary theory. 

Proof. The if direction is an immediate consequence of Lemma 5. 11. To prove the only-if direction, assume that G is a well-behaved theory. We define G as
section_name: Definition 5.7. (3-colorability).

section_content: In this paper, we have extended ACUI-unification in two directions. On one hand, we have considered approximate ACUI-unification w. r. t. three different ways of measuring the degree to which the equations of the unification problem are violated by a given substitution that is not a unifier. For two of these measures, the complexity of the associated decision problem increases from P to NP-complete, whereas for one of them it stays in P. On the other hand, we have extended ACUI-unification to ACUIG-unification, that is, unification in equational theories that are obtained from ACUI by adding a finite set G of ground identities. We were able to show that adding such identities does not change the complexity of the unification problem. Finally, we have combined the two extensions, that is, we have investigated approximate ACUIG-unification. For the measures for which already approximate ACUI-unification is NP-complete, the same holds for approximate ACUIG-unification. For the third measure, which counts the number of violated elements, the situation turns out to be more interesting. We were able to show that there is a finite set G of ground identities such that approximate ACUIG-unification for this fixed theory is NP-complete. But we have also introduced the class of unary ground theories G for which approximate ACUIGunification is in P. It would be interesting to see whether there exist ground theories that are not equivalent to unary theories, but for which approximate ACUIG-unification is still in P. 

These results are of interest for unification theory. In fact, while it was known for quite some time that adding finite sets of ground identities to certain theories such as ACUI leaves the word problem decidable (Marché, 1996; Narendran and Rusinowitch, 1996), no such preservation result was available for unification. In addition, there are only very few results on approximate unification. In (Iranzo and Rubio-Manzano, 2015), the authors introduce what they call proximity-based unification, which basically is an extension of syntactic unification to the approximate case, and use it in the context of fuzzy logic programming. Set unification, which is basically unification modulo ACUI, has drawn considerable attention (Dovier et al., 2006) due to its applications in various areas, such as deductive databases, theorem proving, and static program analysis, and it is conceivable that these applications could also profit from approximate variants. Our results show that the complexity of approximate unification strongly depends on measures used to define the degree to which the equations of the unification problem are violated: while for some measures going from exact unification to approximate unification increases the complexity, it stays the same for other measures. We have no example of nontrivial measures where the complexity decreases in the approximate case, though this is also conceivable. Adding ground identities in the approximate case makes things even more interesting since it may now depend on the ground theory whether the complexity increases or not when going to the approximate case. In the setting of the violated elements measure considered in this paper, where this situation occurs, it would be interesting to see whether one can show a dichotomy result, that is, whether one can prove that, depending on which ground theory G is used, the complexity of approximate ACUIG-unification is either in P or NP-complete. If this is actually the case, the next step would be to attempt a classification of the two cases, that is, come up with conditions that ensure membership in P or NP-completeness. 

In addition to the fact that ACUI is a theory investigated extensively in unification theory and in set unification, our interest in this theory is motivated by the fact that this theory is a common subtheory of the equational theories corresponding to the Description Logics FL 0 (Baader, 1996) and EL (Baader et al., 1999). Unification in DLs (Baader and Morawska, 2009; Baader and Narendran, 2001) was introduced as a novel inference problem that can be used to detect redundancies in knowledge bases, and approximate variants (Baader et al., 2016) were investigated in order to increase the recall of these approaches. The decidability and complexity results for unification in FL 0 and EL respectively shown in (Baader and Narendran, 2001) and (Baader and Morawska, 2009) are restricted to the setting without a background TBox. The big open problem in this area is whether these results can be extended to unification in the presence of general TBoxes, which corresponds to adding a finite set of ground identities to the corresponding equational theory. While a negative result for ACUIG would have implied negative results for the two DLs, the methods used to show the positive results for ACUIG are too simple to be useful for FL 0 and EL. For EL, there are some positive results for the case where the TBox satisfies certain cycle-restrictions (Baader et al., 2012), while for FL 0 there are only positive results for matching in the presence of TBoxes (Baader et al., 2018), but none for unification. 

Approximate unification has been considered for FL 0 (Baader et al., 2016), but with measures that differ from the ones employed in the present paper for ACUI and ACUIG. Basically, instead of constants, the sets that one needs to consider there are sets of words, and the measures employed in (Baader et al., 2016) take the length of these words into account: violations caused by long words are counted as less important than violations caused by shorter words. In addition, in (Baader et al., 2016) only a single equation is considered, and thus measures counting the number of violated equations have not been considered there. It would be interesting to see how approximate unification w. r. t. the measures considered in the present paper behaves for FL 0. For EL, there are, to the best of our knowledge, no results on approximate unification. Here it would be interesting to see whether one can use similarity measures on EL concepts (Lehmann and Turhan, 2012) to define appropriate measures for approximate unification in EL, and whether approximate EL-unification w. r. t. such measures is decidable. The results of the present paper show that the complexity of approximate unification modulo ACUI and ACUIG strongly depends on which measures are used, and which ground theories are considered. We conjecture that the same is true for unification in DLs.
section_name: Conclusion

section_content: † Supported by DFG Graduiertenkolleg 1763 (QuantLA). ‡ Partially supported by DFG Graduiertenkolleg 1763 (QuantLA).