Simplify auxiliary variable handling in CEGQI (#4141)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Mon, 23 Mar 2020 19:04:32 +0000 (14:04 -0500)
committerGitHub <noreply@github.com>
Mon, 23 Mar 2020 19:04:32 +0000 (14:04 -0500)
commitdf7333de4436d846da70857e61cda411d22d02ba
treeb3fe8a20bd3bf89936827eaea0341e049b4116f6
parentdd515b59583cba1afed8fbb583f8012a214feaad
Simplify auxiliary variable handling in CEGQI (#4141)

Fixes #3849 and fixes #4062.

Overall, the effect of this PR is that CEGQI will generate better instantiations more frequently for quantified formulas that involve the introduction of auxiliary variables.

In CEGQI, auxiliary variables introduced in CEX lemmas must be given special treatment (since the instantiations should not involve them, thus they must be solved for as well). Previously, auxiliary variables that are introduced as parts of CEX lemmas were currently assumed to be:
(1) Only occurring from ITE removal, e.g. s[(ite C t1 t2]) ---> s[k] ^ ite( C, k = t1, k = t2 )
(2) Always trivially solvable by looking at which literal was asserted (k = t1 or k = t2).
Both of these assumption do not hold in general (aux variables can come from other kinds of terms e.g. choice functions, and the user can force options that rewrite arithmetic equalities to inequalities).

This makes auxiliary variable handling in CEGQI more robust by treating auxiliary variables as standard variables. Effectively, this means that the entire procedure for determining instantiations is run for auxiliary variables. This PR removes the specific hacks that were used previously that were based on the assumptions above.

Additionally, #3849 triggered a second issue: SyGuS solution reconstruction that involves auxiliary variables that are introduced as part of instantiation lemmas should not be considered valid solutions. Previously, only a warning was given.
src/theory/quantifiers/cegqi/ceg_instantiator.cpp
src/theory/quantifiers/cegqi/ceg_instantiator.h
src/theory/quantifiers/sygus/ce_guided_single_inv.cpp
test/regress/CMakeLists.txt
test/regress/regress1/quantifiers/issue4062-cegqi-aux.smt2 [new file with mode: 0644]