Alchemist: Learning guarded affine functions

Shambwaditya Saha, Pranav Garg, P. Madhusudan

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

Abstract

We present a technique and an accompanying tool that learns guarded affine functions. In our setting, a teacher starts with a guarded affine function and the learner learns this function using equivalence queries only. In each round, the teacher examines the current hypothesis of the learner and gives a counter-example in terms of an input-output pair where the hypothesis differs from the target function. The learner uses these input-output pairs to learn the guarded affine expression. This problem is relevant in synthesis domains where we are trying to synthesize guarded affine functions that have particular properties, provided we can build a teacher who can answer using such counter-examples.We implement our approach and show that our learner is effective in learning guarded affine expressions, and more effective than general-purpose synthesis techniques.

Original languageEnglish (US)
Title of host publicationComputer Aided Verification - 27th International Conference, CAV 2015, Proceedings
EditorsCorina S. Pasareanu, Daniel Kroening, Corina S. Pasareanu, Daniel Kroening
PublisherSpringer
Pages440-446
Number of pages7
ISBN (Print)9783319216898, 9783319216898
DOIs
StatePublished - 2015
Event27th International Conference on Computer Aided Verification, CAV 2015 - San Francisco, United States
Duration: Jul 18 2015Jul 24 2015

Publication series

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

Other

Other27th International Conference on Computer Aided Verification, CAV 2015
Country/TerritoryUnited States
CitySan Francisco
Period7/18/157/24/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Alchemist: Learning guarded affine functions'. Together they form a unique fingerprint.

Cite this