  Syntax-guided synthesis (SyGuS) is a recently proposed framework for program
synthesis problems. The SyGuS problem is to find an expression or program
generated by a given grammar that meets a correctness specification.
Correctness specifications are given as formulas in suitable logical theories,
typically amongst those studied in satisfiability modulo theories (SMT).
  In this work, we analyze the decidability of the SyGuS problem for different
classes of grammars and correctness specifications. We prove that the SyGuS
problem is undecidable for the theory of equality with uninterpreted functions
(EUF).We identify a fragment of EUF, which we call regular-EUF, for which the
SyGuS problem is decidable. We prove that this restricted problem is
EXPTIME-complete and that the sets of solution expressions are precisely the
regular tree languages. For theories that admit a unique, finite domain, we
give a general algorithm to solve the SyGuS problem on tree grammars.
Finite-domain theories include the bit-vector theory without concatenation. We
prove SyGuS undecidable for a very simple bit-vector theory with concatenation,
both for context-free grammars and for tree grammars. Finally, we give some
additional results for linear arithmetic and bit-vector arithmetic along with a
discussion of the implication of these results.
