The article “QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems” omits a condition in one of its observations. Even if this observation is not central to the paper, the omission may cause confusion for the reader. This erratum provides a correction.
The writing of the paper QuickXplain: Preferred Explanations and Relaxations for Over-Constrained Problems has been done under somewhat difficult conditions. A publication at a major AI conference requires more than the description of an algorithm and I therefore tried to find a general concept that provides a clear and simple explanation of what QuickXplain is computing. As I studied the usage of preferences for solving combinatorial problems, I tried to understand QuickXplain from a preference-based perspective and the result promised to be interesting enough for such a publication. I took a lot of notes on how to develop this perspective, but I had not much time to elaborate them all. The topic was no longer part of my job assignment due to a reorganization and I had to find some spare hours to work on the paper. Of course, when no proper conditions for writing a paper are given, errors may happen. Most of them minor and none of them concern the main results of the paper.
Firstly, it needs to be said that Proposition 3 got taken out of its context during writing and does not hold in general. It holds only for problems of a particular form (such as for over-constrained SAT problems where the background is a set of negative clauses and the foreground contains all positive unit clauses of the considered propositional language). Proposition 3 has been included as a side remark and does not contribute to the overall discussion of the paper.
Secondly, there is a series of minor notational issues, which do not hinder an understanding of the paper:
In Proposition 3, the negation of the background set has not been explained. It should be understood as the negation of the conjunction of all the constraints in the background set.
In Proposition 6, the subproblems should not include the full preference order, but only a subset. The order is used to compare the constraints in the foreground of the problem. Hence, the preference order of each subproblem is the intersection of the full preference order with the Cartesian square of the foreground of this subproblem.
Table 4 does not indicate that a logarithm of base two is used to describe the complexity of the algorithm. ►
This web site expresses personal reflections about scientific topics with the purpose of contributing to discussions in scientific communities. As such, this content is not related to any organization, association, or employment.
