Make sygus refinement step more robust to unevaluatable counterexamples (#5102)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Fri, 25 Sep 2020 18:45:38 +0000 (13:45 -0500)
committerGitHub <noreply@github.com>
Fri, 25 Sep 2020 18:45:38 +0000 (13:45 -0500)
commitc59345b93b2ecf3552f5205b312c262a1ae5eab8
tree22496bdc3fe0ff7d5cabcc3be90605b0d02b5d01
parentd05aee802bf93d23193739e8280d2ad5ce7e7469
Make sygus refinement step more robust to unevaluatable counterexamples (#5102)

Currently, the CEGIS refinement loop of the sygus solver may terminate with "unknown" when a duplicate counterexample is generated. This is caused by a candidate t for a conjecture exists f. forall x. G[f, x] such that:

(1) G[t, c] evaluates to a non-constant expression,
(2) ~G[t, k] is satisfiable with model k = c.

Notice this exclusively limited to theories with incomplete functions, e.g. (non-linear) division.

In this case, we know that t is an incorrect solution, but the counterexample we found was not new.

Currently, we abort with "unknown" since the counterexample was not new. After this PR, we exclude t and continue, which is uncontroversially the correct behavior.

This PR moves the resposibility for lemma from synth engine to synth conjecture, which simplifies the behavior of the main check conjecture method.
src/theory/quantifiers/sygus/synth_conjecture.cpp
src/theory/quantifiers/sygus/synth_conjecture.h
src/theory/quantifiers/sygus/synth_engine.cpp