Improvements and fixes for symmetry detection and breaking (#2459)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Tue, 18 Sep 2018 00:51:06 +0000 (19:51 -0500)
committerAndres Noetzli <andres.noetzli@gmail.com>
Tue, 18 Sep 2018 00:51:06 +0000 (17:51 -0700)
commit83be77ff113cbc0357796fb8121091eed2c95ab1
treeda64946f41e6e4ce24ef589ebc7dcd40c1469413
parent603c0ccc4614024dfcd34333cd427ac56e229a47
Improvements and fixes for symmetry detection and breaking (#2459)

This fixes a few open issues with symmetry detection algorithm. It also extends the algorithm to do:
- Alpha equivalence to recognize symmetries between quantified formulas,
- A technique to recognize a subset of variables in two terms are symmetric, e.g. from x in A ^ x in B, we find A and B are interchangeable by treating x as a fixed symbol,
- Symmetry breaking for maximal subterms instead of variables.
src/preprocessing/passes/symmetry_breaker.cpp
src/preprocessing/passes/symmetry_detect.cpp
src/preprocessing/passes/symmetry_detect.h
src/theory/quantifiers/term_util.cpp
test/regress/Makefile.tests
test/regress/regress1/sym/q-constant.smt2 [new file with mode: 0644]
test/regress/regress1/sym/q-function.smt2 [new file with mode: 0644]
test/regress/regress1/sym/qf-function.smt2 [new file with mode: 0644]
test/regress/regress1/sym/sb-wrong.smt2 [new file with mode: 0644]
test/regress/regress1/sym/sym-setAB.smt2 [new file with mode: 0644]