Synthesizing piece-wise functions by learning classifiers

Daniel Neider, Shambwaditya Saha, P. Madhusudan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a novel general technique that uses classifier learning to synthesize piece-wise functions (functions that split the domain into regions and apply simpler functions to each region) against logical synthesis specifications. Our framework works by combining a synthesizer of functions for fixed concrete inputs and a synthesizer of predicates that can be used to define regions. We develop a theory of single-point refutable specifications that facilitate generating concrete counterexamples using constraint solvers. We implement the framework for synthesizing piece-wise functions in linear integer arithmetic, combining leaf expression synthesis using constraint-solving and predicate synthesis using enumeration, and tie them together using a decision tree classifier. We demonstrate that this approach is competitive compared to existing synthesis engines on a set of synthesis specifications.

Original languageEnglish (US)
Title of host publicationTools and Algorithms for the Construction and Analysis of Systems - 22nd International Conference, TACAS 2016 and Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Proceedings
EditorsJean-François Raskin, Marsha Chechik
PublisherSpringer-Verlag Berlin Heidelberg
Pages186-203
Number of pages18
ISBN (Print)9783662496732
DOIs
StatePublished - 2016
Event22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2016 and held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016 - Eindhoven, Netherlands
Duration: Apr 2 2016Apr 8 2016

Publication series

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

Other

Other22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2016 and held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016
CountryNetherlands
CityEindhoven
Period4/2/164/8/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Synthesizing piece-wise functions by learning classifiers'. Together they form a unique fingerprint.

Cite this