  A fundamental challenge in synthesis from examples is designing a learning
algorithm that poses the minimal number of questions to an end user while
guaranteeing that the target hypothesis is discovered. Such guarantees are
practically important because they ensure that end users will not be
overburdened with unnecessary questions.
  We present SPEX -- a learning algorithm that addresses the above challenge.
SPEX considers the hypothesis space of formulas over first-order predicates and
learns the correct hypothesis by only asking the user simple membership queries
for concrete examples. Thus, SPEX is directly applicable to any learning
problem that fits its hypothesis space and uses membership queries.
  SPEX works by iteratively eliminating candidate hypotheses from the space
until converging to the target hypothesis. The main idea is to use the
implication order between hypotheses to guarantee that in each step the
question presented to the user obtains maximal pruning of the space. This
problem is particularly challenging when predicates are potentially correlated.
  To show that SPEX is practically useful, we expressed two rather different
applications domains in its framework: learning programs for the domain of
technical analysts (stock trading) and learning data structure specifications.
The experimental results show that SPEX's optimality guarantee is effective: it
drastically reduces the number of questions posed to the user while
successfully learning the exact hypothesis.
