Fix soundess issue for bags with negative multiplicity (#7539)
authormudathirmahgoub <mudathirmahgoub@gmail.com>
Sun, 31 Oct 2021 14:07:36 +0000 (09:07 -0500)
committerGitHub <noreply@github.com>
Sun, 31 Oct 2021 14:07:36 +0000 (14:07 +0000)
commit08800bd63da929fd0439d0e743ace1a71aeffa14
tree8b1326ea4f67f5b9e8ed5c74cef323f0e2303d6b
parentf80a5ed2b00cf0bc1d9ee8210dc64b3df7f8e6b4
Fix soundess issue for bags with negative multiplicity (#7539)

This PR fixes soundness issues found by cvc5 fuzzy sygus when it answers unsat for sat problems.
One error was with the rewrite rule (bag.count x (bag x c) = c which did not account for cases when c is negative.
This conflicts with fact that all multiplicities are non-negative.
Another error was that the difference_remove inference rule didn't consider the negative case for (count e B)

(= (count e (difference_remove A B)) (ite (=  (count e B) 0) (count e A) 0))) ; not enough
(= (count e (difference_remove A B)) (ite (<= (count e B) 0) (count e A) 0))) ; the right rule
src/theory/bags/bags_rewriter.cpp
src/theory/bags/bags_rewriter.h
src/theory/bags/inference_generator.cpp
src/theory/bags/inference_generator.h
src/theory/inference_id.cpp
src/theory/inference_id.h
test/regress/CMakeLists.txt
test/regress/regress1/bags/fuzzy4.smt2 [new file with mode: 0644]
test/regress/regress1/bags/fuzzy5.smt2 [new file with mode: 0644]
test/unit/theory/theory_bags_rewriter_white.cpp