Using contextual information in sequential search for grammatical optimization problems

Research output: Chapter in Book/Report/Conference proceedingsConference contributionpeer-review

Abstract

Automated synthesis of complex programs is still an unsolved problem even though some successes have been achieved recently for relatively contrived and specialized settings. One possible approach to automated programming is genetic programming, however, a diverse set of alternative techniques are possible which makes it rather difficult to make general assertions about characteristics or structure of automated programming tasks. We have therefore defined the concept of grammatical optimization problems for problems with an objective function and grammar constraint for valid solutions. The problem of synthesizing computer programs can be formulated as a grammatical optimization problem. In this contribution we describe our idea of using contextual information for guiding the search process. First, we describe how the search process can be described as a sequential decision process and show how Monte-Carlo tree search is one way to optimize this decision process. Based on the formulation as a sequential decision process we explain how lexical, syntactical, as well as program state can be used for guiding the search process. This makes it possible to learn problem structure in a way that goes beyond what is possible with simple Monte-Carlo tree search.

Original languageEnglish
Title of host publicationComputer Aided Systems Theory – EUROCAST 2015 - 15th International Conference, Revised Selected Papers
EditorsFranz Pichler, Roberto Moreno-Díaz, Alexis Quesada-Arencibia
PublisherSpringer
Pages417-424
Number of pages8
ISBN (Print)9783319273396
DOIs
Publication statusPublished - 2015
Event15th International Conference on Computer Aided Systems Theory, Eurocast 2015 - Las Palmas, Gran Canaria, Spain
Duration: 8 Feb 201513 Feb 2015
http://eurocast2015.fulp.ulpgc.es/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9520
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Computer Aided Systems Theory, Eurocast 2015
Country/TerritorySpain
CityLas Palmas, Gran Canaria
Period08.02.201513.02.2015
Internet address

Keywords

  • Automated programming
  • Genetic programming
  • Monte-Carlo tree search
  • Sequential decision processes

Fingerprint

Dive into the research topics of 'Using contextual information in sequential search for grammatical optimization problems'. Together they form a unique fingerprint.

Cite this