<p>Suppose we are given a standard <a href="https://en.wikipedia.org/wiki/Unification_(computer_science)" rel="nofollow noreferrer">first-order unification</a> problem, represented as a set $D$ of term equality constraints, such that the system $D$ as a whole is unsatisfiable. Consider the minimal unsatisfiable constraint sets of this problem. (A set $C \subseteq D$ of type constraints is a minimal unsatisfiable constraint set if $C$ is unsatisfiable and every strict subset of $C$ is satisfiable.)</p>

<p>Define the <em>involved set</em> for $D$ as the set of all constraints in $D$ that are members of some minimal unsatisfiable constraint set&mdash;i.e. the union of all minimal unsatisfiable constraint sets. It would be very convenient if we could compute the involved set efficiently, because this is the set of constraints that are "involved" in making the problem instance unsatisfiable.</p>

<p>The question is, is it possible to compute the involved set for an arbitrary unification problem in polynomial time?</p>

<hr>

<p>I've done some thought and research on this problem and haven't found a solution yet. In the remainder of this question, I will explain some of the ideas I have considered for solving the problem.</p>

<h2>Independence systems</h2>

<p>Since unification problems are constraint satisfaction problems, the satisfiable subsets of a given unification problem form an <a href="http://ics.upjs.sk/~semanisin/HereditarniaPM/PrezSyNe.pdf" rel="nofollow noreferrer">independence system</a>. In the language of independence systems, a satisfiable constraint set is an independent set, an unsatisfiable constraint set is a dependent set, a maximal satisfiable constraint set is a base, and a minimal unsatisfiable constraint set is a circuit. Several algorithms in the literature on finding minimal unsatisfiable constraint sets in unification problems actually only need access to an oracle that supports efficiently testing at what point incrementally adding one constraint at a time to an independent set makes the set dependent. For example:</p>

<ul>
<li>We can find <em>a single arbitrary</em> minimal unsatisfiable constraint set in $O(|D|^2)$ time. The algorithm to do this is described in <a href="https://pdfs.semanticscholar.org/fd20/6cdb28092b9ad448515c6866b63c75e931d4.pdf" rel="nofollow noreferrer">Stuckey, Sulzmann, and Wazny (2003). "Interactive Type Debugging in Haskell"</a>, section 7.1.</li>
<li>Stuckey et al. (2003) also note that we can find the set of constraints that are members of <em>every</em> minimal unsatisfiable constraint set&mdash;i.e. the <em>intersection</em> of all minimal unsatisfiable constraint sets&mdash;in $O(|D|^2)$ time, because these are exactly the constraints $e \in D$ where $D \setminus \{ e \}$ is satisfiable.</li>
<li>We can use the existence of an incremental independence oracle to enumerate all of the minimal unsatisfiable constraint sets more efficiently than if we simply listed every subset of constraints and checked it for independence. For an example of such an algorithm, see <a href="https://pdfs.semanticscholar.org/4619/116d00e2b29acf97621438a5f2f639f0bae1.pdf" rel="nofollow noreferrer">Bailey and Stuckey (2005). "Discovery of Minimal Unsatisfiable Subsets of Constraints Using Hitting Set Dualization."</a> Unfortunately, we can't simply enumerate all of the minimal unsatisfiable constraint sets and take their union explicitly, because a unification problem can have exponentially many minimal unsatisfiable sets.</li>
</ul>

<p>I have not found an algorithm that allows computing the union of all circuits in polynomial time given only access to an incremental independence oracle, and my gut feeling is that it is probably not possible. (I'd love to be wrong on this.)</p>

<p>Because the satisfiable subsets of a unification problem form an independence system, it is natural to ask whether they also satisfy the exchange property so that they form a <a href="https://en.wikipedia.org/wiki/Matroid" rel="nofollow noreferrer">matroid</a>. Unfortunately, in general they do not: $A = \{ a \sim \mathsf{Bool}, a \sim b, b \sim \mathsf{Bool} \}$ is an independent set that is larger than the independent set $B = \{ a \sim \mathsf{Int}, b \sim \mathsf{Float} \}$, but no element of $A \setminus B$ can be added to $B$ without making it dependent.</p>

<h2>Type graphs and error paths</h2>

<p>If the unification problem contains only constant and variable terms but no function symbols with arguments, then we can compute the involved set efficiently. This is because, in this restricted case, a constraint set is minimal unsatisfiable if and only if it is the set of edges comprising some simple path between two conflicting vertices in the type graph for the unification problem. (The concept of type graphs is described in detail in chapter 7 of <a href="http://www.open.ou.nl/bhr/TopQuality.pdf" rel="nofollow noreferrer">Heeren (2005). <em>Top Quality Type Error Messages</em>.</a>) Finding the set of all edges on any simple path between a subset of the vertices in a connected graph can be done in linear time by <a href="http://stackoverflow.com/q/10825249">a straightforward reduction to the biconnected components problem for the graph</a>.</p>

<p>Function symbols seem to make the problem more complicated, because the type graph can now contain exponentially-long shortest error paths (in the sense of Heeren (2005)). So if we want to find the involved set efficiently, we need a way of determining the set of edges that are on some error path between conflicting vertices without having to explicitly write down any error paths.</p>

<p>With function symbols, we also have to account for the possibility of occurs check errors in addition to function head clashes. Occurs check errors can be isolated efficiently by finding the strongly-connected components of the unified sets of the type graph, as described in Heeren (2005), but this doesn't give an involved set of constraints.</p>

CC BY-SA 3.0
2017-06-30T12:45:21.753Z
Why are you expecting this minimal set to be unique? Or are you just asking for *a* minimal set?
cody
CC BY-SA 3.0
2017-06-30T17:23:46.930Z
@cody I am not expecting a unique minimal unsatisfiable set. I state explicitly that there can be exponentially-many such sets for a given input problem, and reference an algorithm for finding an arbitrary minimal unsatisfiable set. I am asking for an efficient way of calculating _the union of all_ minimal unsatisfiable sets for a given input problem.
Aaron Rotenberg
<ds.algorithms><graph-algorithms><lo.logic>
Efficiently computing the union of all minimal unsatisfiable constraint sets in a first-order unification problem
Aaron Rotenberg
# Efficiently computing the union of all minimal unsatisfiable constraint sets in a first-order unification problem

(Asked by: username_0 on 2017-06-27)

Suppose we are given a standard [first-order unification](https://en.wikipedia.org/wiki/Unification_(computer_science)) problem, represented as a set $D$ of term equality constraints, such that the system $D$ as a whole is unsatisfiable. Consider the minimal unsatisfiable constraint sets of this problem. (A set $C \subseteq D$ of type constraints is a minimal unsatisfiable constraint set if $C$ is unsatisfiable and every strict subset of $C$ is satisfiable.)

Define the *involved set* for $D$ as the set of all constraints in $D$ that are members of some minimal unsatisfiable constraint set—i.e. the union of all minimal unsatisfiable constraint sets. It would be very convenient if we could compute the involved set efficiently, because this is the set of constraints that are "involved" in making the problem instance unsatisfiable.

The question is, is it possible to compute the involved set for an arbitrary unification problem in polynomial time?

---

I've done some thought and research on this problem and haven't found a solution yet. In the remainder of this question, I will explain some of the ideas I have considered for solving the problem.

## Independence systems

Since unification problems are constraint satisfaction problems, the satisfiable subsets of a given unification problem form an [independence system](http://ics.upjs.sk/~semanisin/HereditarniaPM/PrezSyNe.pdf). In the language of independence systems, a satisfiable constraint set is an independent set, an unsatisfiable constraint set is a dependent set, a maximal satisfiable constraint set is a base, and a minimal unsatisfiable constraint set is a circuit. Several algorithms in the literature on finding minimal unsatisfiable constraint sets in unification problems actually only need access to an oracle that supports efficiently testing at what point incrementally adding one constraint at a time to an independent set makes the set dependent. For example:

* We can find *a single arbitrary* minimal unsatisfiable constraint set in $O(|D|^2)$ time. The algorithm to do this is described in [Stuckey, Sulzmann, and Wazny (2003). "Interactive Type Debugging in Haskell"](https://pdfs.semanticscholar.org/fd20/6cdb28092b9ad448515c6866b63c75e931d4.pdf), section 7.1.
* Stuckey et al. (2003) also note that we can find the set of constraints that are members of *every* minimal unsatisfiable constraint set—i.e. the *intersection* of all minimal unsatisfiable constraint sets—in $O(|D|^2)$ time, because these are exactly the constraints $e \in D$ where $D \setminus \{ e \}$ is satisfiable.
* We can use the existence of an incremental independence oracle to enumerate all of the minimal unsatisfiable constraint sets more efficiently than if we simply listed every subset of constraints and checked it for independence. For an example of such an algorithm, see [Bailey and Stuckey (2005). "Discovery of Minimal Unsatisfiable Subsets of Constraints Using Hitting Set Dualization."](https://pdfs.semanticscholar.org/4619/116d00e2b29acf97621438a5f2f639f0bae1.pdf) Unfortunately, we can't simply enumerate all of the minimal unsatisfiable constraint sets and take their union explicitly, because a unification problem can have exponentially many minimal unsatisfiable sets.

I have not found an algorithm that allows computing the union of all circuits in polynomial time given only access to an incremental independence oracle, and my gut feeling is that it is probably not possible. (I'd love to be wrong on this.)

Because the satisfiable subsets of a unification problem form an independence system, it is natural to ask whether they also satisfy the exchange property so that they form a [matroid](https://en.wikipedia.org/wiki/Matroid). Unfortunately, in general they do not: $A = \{ a \sim \mathsf{Bool}, a \sim b, b \sim \mathsf{Bool} \}$ is an independent set that is larger than the independent set $B = \{ a \sim \mathsf{Int}, b \sim \mathsf{Float} \}$, but no element of $A \setminus B$ can be added to $B$ without making it dependent.

## Type graphs and error paths

If the unification problem contains only constant and variable terms but no function symbols with arguments, then we can compute the involved set efficiently. This is because, in this restricted case, a constraint set is minimal unsatisfiable if and only if it is the set of edges comprising some simple path between two conflicting vertices in the type graph for the unification problem. (The concept of type graphs is described in detail in chapter 7 of [Heeren (2005). *Top Quality Type Error Messages*.](http://www.open.ou.nl/bhr/TopQuality.pdf)) Finding the set of all edges on any simple path between a subset of the vertices in a connected graph can be done in linear time by [a straightforward reduction to the biconnected components problem for the graph](http://stackoverflow.com/q/10825249).

Function symbols seem to make the problem more complicated, because the type graph can now contain exponentially-long shortest error paths (in the sense of Heeren (2005)). So if we want to find the involved set efficiently, we need a way of determining the set of edges that are on some error path between conflicting vertices without having to explicitly write down any error paths.

With function symbols, we also have to account for the possibility of occurs check errors in addition to function head clashes. Occurs check errors can be isolated efficiently by finding the strongly-connected components of the unified sets of the type graph, as described in Heeren (2005), but this doesn't give an involved set of constraints.

**Tags:** ds.algorithms, graph-algorithms, lo.logic

> **Comments:**
> **username_1**: Why are you expecting this minimal set to be unique? Or are you just asking for *a* minimal set?  
> **username_0**: @username_1 I am not expecting a unique minimal unsatisfiable set. I state explicitly that there can be exponentially-many such sets for a given input problem, and reference an algorithm for finding an arbitrary minimal unsatisfiable set. I am asking for an efficient way of calculating _the union of all_ minimal unsatisfiable sets for a given input problem.  

---

## 0 answers

