- author = "Thomas Welsch",
- title = "A Framework for Program Synthesis on Conditional Domains",
- school = "School of Electrical Engineering, Electronics and Computer Science, University of Liverpool",
- year = "2023",
- address = "UK",
- month = jul,
- keywords = "genetic algorithms, genetic programming, SyGuS LIA, Counterexample-Driven Genetic Program, CDGP, Synthesis through Unification Genetic Programming, STUN GP, LearningSMS, CLIA, Java, Lexicase, Search-Based Program Synthesis, SBPS",
-
URL = "
https://livrepository.liverpool.ac.uk/id/eprint/3180027",
-
URL = "
https://livrepository.liverpool.ac.uk/3180027/1/201301110_Jul2023.pdf",
-
DOI = "
doi:10.17638/03180027",
- size = "61 pages",
-
abstract = "Program synthesis is the automatic generation of
computer programs from user-specified requirements. In
this thesis we present a framework, Set and Map
Synthesis (SMS), for program synthesis problems where
the program to synthesize requires an if-than-else
tree. The SMS framework separates synthesis into two
tasks: the synthesis of a set of programs that can
serve as the subprograms of the if-than-else tree and a
corresponding set of predicates that hold if and only
if a subprogram is correct. The key idea is that this
approach can be used to significantly improve the
performance of learning methods on synthesis tasks.
We formalize this approach and discuss a preliminary implementation of its concepts that was achieved by Synthesis through Unification GP (STUN GP). This built on previous work using Genetic Programming for program synthesis and achieved significant improvements in performance. We then discuss further improvements made in a second implementation of the SMS framework, LearningSMS. LearningSMS uses divide-and-conquer tactics to continuously decompose the input space until it is restricted enough to be solved directly by a stochastic learning method. It is extensible to any learning method and our implementation with Genetic Programming achieved results within a constant factor of the state-of-the-art synthesizers on the Syntax Guided Synthesis (SyGuS) Conditional Linear Integer Arithmetic (CLIA) benchmarks. This represents a significant improvement over previous attempts to apply learning methods to program synthesis problem",
- notes = "Supervisors: Vitaliy Kurlin and Patrick Totzke",
