Write a Blog >>
Wed 21 Jun 2017 15:30 - 15:55 at Auditorium, Vertex Building - Analysis and Synthesis Chair(s): Anders Møller

Synthesis from examples enables non-expert users to generate programs by specifying examples of their behavior. A domain-specific form of such synthesis has been recently deployed in a widely used spreadsheet software product. In this paper we contribute to foundations of such techniques and present a complete algorithm for synthesis of a class of recursive functions defined by structural recursion over a given algebraic data type definition. The functions we consider map an algebraic data type to a string; they are useful for, e.g., pretty printing and serialization of programs and data. We formalize our problem as learning deterministic sequential top-down tree-to-string transducers with a single state.

The first problem we consider is learning a tree-to-string transducer from any set of input/output examples provided by the user. We show that this problem is NP-complete in general, but can be solved in polynomial time under a (practically useful) closure condition that each subtree of a tree in the input/output example set is also part of the input/output examples.

Because coming up with relevant input/output examples may be difficult for the user while creating hard constraint problems for the synthesizer, we also study a more automated active learning scenario in which the algorithm chooses the inputs for which the user provides the outputs. Our algorithm asks a worst-case linear number of queries as a function of the size of the algebraic data type definition to determine a unique transducer.

To construct our algorithms we present two new results on formal languages.

First, we define a class of word equations, called sequential word equations, for which we prove that satisfiability can be solved in deterministic polynomial time. This is in contrast to the general word equations for which the best known complexity upper bound is PSPACE.

Second, we close a long-standing open problem about the asymptotic size of test sets for context-free languages. A test set of a language of words $L$ is a subset $T$ of $L$ such that any two word homomorphisms equivalent on $T$ are also equivalent on $L$. We prove that it is possible to build test sets of cubic size for context-free languages, matching for the first time the lower bound found 20 years ago.

Wed 21 Jun

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

15:30 - 17:10
Analysis and SynthesisECOOP Research Papers at Auditorium, Vertex Building
Chair(s): Anders Møller Aarhus University
15:30
25m
Talk
Proactive Synthesis of Recursive Tree-to-String Functions from Examples
ECOOP Research Papers
Mikaël Mayer EPFL, Switzerland, Jad Hamza LIAFA, Université Paris Diderot, Viktor Kunčak EPFL, Switzerland
Link to publication Media Attached
15:55
25m
Talk
Speeding Up Maximal Causality Reduction with Static Dependency Analysis
ECOOP Research Papers
Shiyou Huang Texas A&M University, Jeff Huang Texas A&M University
Link to publication Media Attached
16:20
25m
Talk
Mailbox Abstractions for Static Analysis of Actor Programs
ECOOP Research Papers
Quentin Stiévenart Vrije Universiteit Brussel, Belgium, Jens Nicolay Vrije Universiteit Brussel, Belgium, Wolfgang De Meuter Vrije Universiteit Brussel, Coen De Roover Vrije Universiteit Brussel
Link to publication Pre-print Media Attached
16:45
25m
Talk
What’s the Optimal Performance of Precise Dynamic Race Detection? – A Redundancy Perspective
ECOOP Research Papers
Jeff Huang Texas A&M University, Arun Krishnakumar Rajagopalan Texas A&M University
Link to publication Media Attached