Add Card solver to bags (#7986)
authormudathirmahgoub <mudathirmahgoub@gmail.com>
Wed, 26 Jan 2022 18:41:26 +0000 (12:41 -0600)
committerGitHub <noreply@github.com>
Wed, 26 Jan 2022 18:41:26 +0000 (18:41 +0000)
commit51d731ec403becd8a46e02933112ff2fc6b310e9
tree3a151d1d5f6c7af7b4215aec650bb57eaae8a212
parent7fd60d0f147b8afd5d6678b2eb6951409b2c8bea
Add Card solver to bags (#7986)

This PR avoids reducing bag.card terms with quantifiers unless it is needed.
It does so by building a cardinality graph for bags and adds appropriate constraints on internal nodes in the graph and min size constraints for the leaves.
This works for many of the benchmarks where each internal node has a single set of children.
Reduction lemmas are only generated when there are multiple sets of children.
Cardinality for bag.difference_remove and bag.duplicate_removal is not supported and would handled in future PR
14 files changed:
src/CMakeLists.txt
src/theory/bags/card_solver.cpp [new file with mode: 0644]
src/theory/bags/card_solver.h [new file with mode: 0644]
src/theory/bags/inference_generator.cpp
src/theory/bags/inference_generator.h
src/theory/bags/solver_state.cpp
src/theory/bags/solver_state.h
src/theory/bags/strategy.cpp
src/theory/bags/strategy.h
src/theory/bags/theory_bags.cpp
src/theory/bags/theory_bags.h
test/regress/CMakeLists.txt
test/regress/regress1/bags/card3.smt2 [new file with mode: 0644]
test/regress/regress1/bags/fol_0000119.smt2 [new file with mode: 0644]