1

I have two series of constraints S and S', they describe possibly infinitely large sets. Say for example S: x <= 10 and y <= x and S': x <= 20 and y <= 20. Now I want to know if S is a subset of S'?

I thought I could try to solve something like: S' and not (S and S'), if it couldn't find a solution S is a subset of S'.

How would I put this in prolog, is this a reliable solution? I am using gprolog but I can switch to another implementation.

kaibakker
  • 301
  • 3
  • 13
  • 1
    Are the less than or equal the only type of constraints, In general this is an undecidable problem... – Willem Van Onsem May 18 '15 at 13:07
  • There are some more types of constraints, like: ==, !=, <=, >=. Is this really undecidable, I hoped I could just solve it with a solver.. – kaibakker May 18 '15 at 13:39
  • on a finite domain, will be decidable. You can use implication #==> and domain enumeration, but don't expect anything fast enough to be usable on practical tasks... – CapelliC May 18 '15 at 16:41
  • 3
    Isn't it sufficient to ensure that there is no solution to (in your notation) `(not S') and S`? – false May 18 '15 at 17:09
  • Please also see [a related question](http://stackoverflow.com/q/4089885/1613573) and the answers. – mat May 19 '15 at 11:52

1 Answers1

1

The comment by @false is correct, as far as I can see: given two sets S and S': if S is a subset of S', then the intersection of the complement of S' and S should be the empty set (there are no elements outside of S' that are elements of S).

It seems that constraint programming over finite domains should do the trick if you are dealing with integers. Using SWI-Prolog 7.3, and doing your example manually, I get:

?- use_module(library(clpfd)).
true.

?- \+ ( X #=< 10, Y #=< X, #\ X #=< 20 #\/ #\ Y #=< 20 ).
true.

The second query should read:

\+ ( % succeed if no solutions
    X #=< 10, Y #=< X, % set S and...
    #\ X #=< 20 #\/ #\ Y #=< 20 % complement of set S' (De Morgan's Law)
).

I think that the complement of S' could have also been written as:

\# (X #=< 20 #/\ Y #=< 20)

If you want to have a more general solution you would have to figure out a way to find the complements of an arbitrary set of constraints. Note that you can use the Prolog conjunction (the comma) as a logical AND, but you cannot use the disjunction as an OR.

  • CLP(Q) is most called for in this situation. While SWI's CLP(fd) actually a CLP(Z) is exemplarily correct (like SICStus), it still makes a statements about certain integers. There might be solutions in Q that do not exist in Z. – false May 19 '15 at 12:20
  • @false Need more to understand your comment: do you mean that it is better to represent the X and Y as a rational, or is it something else that makes CLP(Q) the correct choice? –  May 19 '15 at 12:27
  • OP did not state what the variables are about ; so this suggests rather Q than Z. OTOH, in CLP(Q), you have to do the negation manually. So you have to manually translate `not X #> Y` to `X #=< Y` etc. – false May 19 '15 at 12:51
  • @false There are a bunch of details OP has not provided, indeed –  May 19 '15 at 13:02