Fix sets cardinality cycle rule (#4392)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Sun, 26 Apr 2020 05:05:28 +0000 (00:05 -0500)
committerGitHub <noreply@github.com>
Sun, 26 Apr 2020 05:05:28 +0000 (22:05 -0700)
commit8476f38b6a3288eebe50e12a2dc6b76a10b65aae
tree7efd22b84214e599d6f43aeb1139fc34469e1b5c
parent1cacd328b60713e21af6836c65007ebe3bfffa81
 Fix sets cardinality cycle rule (#4392)

Fixes #4391.

The sets cardinality cycle rule is analogous to the S-Cycle rule for strings (see Liang et al CAV 2014). This rule is typically never applied but can be applied in rare cases where theory combination does not determine a correct arrangement of equalities over sets terms that is consistent with the arithmetic arrangement of their cardinalities at full effort. Notice the regression from #4391 has non-linear arithmetic, (mod 0 d), which is translated to UF.

The cardinality cycle rule had a bug: it assumed that cycles that were encountered were loops e1 = e2 = ... = e1 but in general they can be lassos e1 = ... = e2 = ... = e2. This ensures the Venn region cycle e2 = ... = e2 is the conclusion in this case, instead of unsoundly concluding e1 = ... = e2.

Strings does not have a similar issue:
https://github.com/CVC4/CVC4/blob/master/src/theory/strings/core_solver.cpp#L488
Here, when a cycle is encountered, it is processed at the point in traversal where the loop is closed.

This is not critical for SMT-COMP but should be in the 1.8 release.
src/theory/sets/cardinality_extension.cpp
test/regress/CMakeLists.txt
test/regress/regress1/sets/issue4391-card-lasso.smt2 [new file with mode: 0644]