- author = "Stefan Forstenlechner",
- title = "Program Synthesis with Grammars and Semantics in Genetic Programming",
- school = "University College Dublin",
- year = "2019",
- address = "Ireland",
- month = jan,
- keywords = "genetic algorithms, genetic programming, grammar, program synthesis, General Program Synthesis Benchmark Suite, Grammar Design, Semantic Operators, SCPS, ESMPS",
-
URL = "
https://www.smurfitschool.ie/facultyresearch/phdresearch/phdgraduates/stefanforstenlechner/",
-
URL = "
http://ncra.ucd.ie/papers/PhDThesis_forstenlechner_submitted.pdf",
- size = "249 pages",
-
abstract = "Program synthesis is an important field that has many
use cases like bug fixing, automating repetitive tasks
and discovering new algorithms. One way to approach
program synthesis tasks is to specify a grammar that
defines all possible programs that can be created and
using a search algorithm like genetic programming to
create a program. Although using grammars has the
advantage that created programs are syntactically
correct, the grammar has to be defined for each problem
tackled.
The focus of this thesis is to introduce a grammar design approach that provides the ability to tackle arbitrary program synthesis problems from input/output examples. The grammars will not be required to be tailored to a specific problem, and in contrast to many existing approaches, the code of the produced programs will be in a programming language used by practitioners. The grammar design approach is studied on a range of program synthesis problems throughout the thesis and shows results that are competitive to state of the art systems.
As the search for programs with genetic programming is often done on the syntactic representation without considering the behaviour or semantics of a program, the introduction of semantic operators for program synthesis will be investigated. While in other problem domains, semantic operators have improved search performance, no such operators are available for the program synthesis domain. A definition of semantics in program synthesis will be provided, and multiple semantic measures and operators will be studied on the basis of this definition. The results show that novel semantic crossover and mutation operators for genetic programming can outperform traditional operators that do not consider semantic information.",
-
notes = "UCD student number: 14204817. SFI
13/IA/1850
Supervisor: Professor Michael O'Neill",
