Decidable Synthesis of Programs with Uninterpreted Functions
share
We identify a decidable synthesis problem for a class of programs of unbounded size with conditionals and iteration that work over infinite data domains. The programs in our class use uninterpreted functions and relations, and abide by a restriction called coherence that was recently identified to yield decidable verification. We formulate a powerful grammar-restricted (syntax-guided) synthesis problem for coherent uninterpreted programs and show the problem to be decidable. We identify its precise complexity, which is doubly exponential in the set of program variables and linear in the size of the grammar. The decision procedure uses tree automata which accept finite syntax trees of all correct programs. It checks that each of the infinitely many executions for a given program is correct using a finite memory streaming congruence closure algorithm. We also study variants of uninterpreted program synthesis: synthesis of transition systems with lower complexity (EXPTIME), synthesis of recursive programs, and synthesis of Boolean programs. We also show undecidability results that argue the necessity of our restrictions.
READ FULL TEXT