Alchemist: Learning guarded affine functions

Shambwaditya Saha, Pranav Garg, P. Madhusudan

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


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
Number of pages7
ISBN (Print)9783319216898, 9783319216898
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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other27th International Conference on Computer Aided Verification, CAV 2015
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this