The 2nd Syntax Guided Synthesis Competition will take place as a satellite event of CAV and SYNT 2015 .

Benchmark submission opens: 1 May 2015

Benchmark submission deadline: 31 may 2015

Solver submission opens: 15 May 2015

Solver submission deadline: ~~15 June 2015~~ 29 June 2015

Competition date: 28 June 2015

Results published: ~~10 July 2015~~ 15 July 2015

Solver presentations: 18 July 2015 (with SYNT)

Benchmark submission

Solver submission

This is a call for participation for the Second Syntax-Guided Synthesis Competition to be organized as a satellite event of SYNT/CAV 2015. The classical formulation of the program-synthesis problem is to find a program that meets a correctness specification given as a logical formula. Recent work on program synthesis and program optimization illustrates many potential benefits of allowing the user to supplement the logical specification with a syntactic template that constrains the space of allowed implementation. The motivation is twofold. First, narrowing the space of implementations makes the synthesis problem more tractable. Second, providing a specific syntax can potentially lead to better optimizations.

The input to the syntax-guided synthesis problem (SyGuS) consists of a background theory, a semantic correctness specification for the desired program given by a logical formula, and a syntactic set of candidate implementations given by a grammar. The computational problem then is to find an implementation from the set of candidate expressions that satisfies the specification in the given theory.

The SyGuS-Comp competition will allow solvers to compete on a collection of benchmarks and advance the state-of-the-art for program-synthesis tools. The competition is organized as part of NSF Expeditions in Computing project ExCAPE by Rajeev Alur (Penn), Dana Fisman (Penn), Rishabh Singh (Microsoft Research) and Armando Solar-Lezama (MIT). For questions regarding the competition please contact the organizers at sygus-organizers@seas.upenn.edu.

In addition to a general track (similar to last year's competition), we will also be having two special tracks: 1) Invariant Synthesis track, and 2) Conditional Linear Integer Arithmetic track. The Invariant Synthesis track would consist of invariant synthesis benchmarks over linear integer arithmetic where the correctness specification would be structured in the form of pre-condition, post-condition, and a transition relation. The Conditional Linear Integer Arithmetic track would consist of synthesis benchmarks where the grammar of candidate implementations will be fixed generating expressions in the theory of linear integer arithmetic with Boolean conditionals. [See here the enhanced SyGuS-IF syntax.]

We will evaluate the solvers on a subset of public benchmarks and some secret benchmarks. The benchmarks domain areas include bit-vector manipulation, including bit-vector algorithms, concurrency, robotics, and invariant generation. We are still finalizing the set of benchmarks, and would appreciate your contribution especially for the newer tracks of invariant synthesis and conditional linear integer arithmetic. [Benchmark submission link]

Evaluation of the solvers will be done on the StarExec system (200 dual quad-core machines with 256GB memory each). The solvers would be run with a TIMEOUT value. The SyGuS-correctness checker, as well as two initial solvers (enumerative and stochastic) are available on the SyGuS community at StarExec. Candidate participants are invited to register to StarExec where they can easily and discreetly compare their solvers to the initial ones against the public benchmarks.

The solvers scores will be based primarily on the number of benchmark solved and the solving time, and secondarily on the succinctness of the synthesized solution.

We expect the tool developers to test their solvers on the public benchmarks, and submit the solver binaries by the Solver submission deadline. Each solver submission should be accompanied by a 1-2 page (IEEE format) description of the key ideas of the solvers. [Solver submission link]

All benchmarks will be made public after the competition. We encourage the tool developers to make their solvers open-source, but participants are welcomed to submit binaries of proprietary tools as well.