Adding non-strict comparisons

The algorithm solve_constraints can be modified to deal with non-strict comparisons of the form od(a,b) <<= od(c,d) by, intuitively, marking the edge ab as ``short'' on each iteration if the edge cd has been found to be short.

Specifically, in algorithm solve_constraints, we make the following changes:

• The algorithm takes two parameters: S, the set of strict constraints, and W, the set of non-strict constraints.
• Replace the line

  H := the connected components of the shorts of S
  

  with the following code:

  1.   H := the shorts of S; 
  2.   repeat H := the connected components of H; 
  3.          for each weak constraint od(a,b) <<= od(c,d) 
  4.              if cd is in H then add ab to H endif endfor
  5.   until no change has been made to H in the last iteration.
  

The proof that the revised algorithm is correct is only a slight extension of the proof of theorem 1 and is given in the appendix.

Optimizing this algorithm for efficiency is a little involved, not only because of the new operations that must be included, but also because there are now four parameters -- n, the number of symbols; e, the number of edges mentioned; s, the number of strict comparison; and w, the number of non-strict comparisons -- and the optimal implementation varies depending on their relative sizes. In particular, either s or w, though not both, may be much smaller than n, and each of these cases requires special treatment for optimal efficiency. The best implementation we have found for the case where both s and w are O(n) has a running time of O(max (n³, nw, s)). The details of the implementation are straightforward and not of sufficient interest to be worth elaborating here.

An immediate consequence of this result is that a couple of problems of inference are easily computed:

• To determine whether a constraint C is the consequence of a set of constraints S, let T be the union of S with the negation of C, and check T for consistency. If T is inconsistent then C is a consequence of S. Note that the negation of the constraint od(a,b) << od(c,d) is the constraint od(c,d) <<= od(a,b).
• To determine whether two sets of constraints are logically equivalent, check that each constraint in the first is a consequence of the second, and vice versa.