Digital Library[ Search Result ]

Search : [ author: Woosuk Lee ] (2)

Improving Counterexample-Guided Bidirectional Inductive Synthesis by an Incremental Approach

Yongho Yoon, Woosuk Lee, Kwangkeun Yi

http://doi.org/10.5626/JOK.2023.50.12.1091

One of the sources of inefficiency in counterexample-guided inductive synthesis algorithms is the fresh restart of inductive synthesis for each iteration. In this paper, we propose an incremental approach for the generalized counterexample-guided bidirectional inductive synthesis algorithm. The incremental algorithm reuses knowledge from the last iteration therefore reducing the search space, and making the remaining search faster. We applied our approach to the state-of-the-art bidirectional inductive synthesis algorithm, Simba, which is based on iterative forward-backward abstract interpretation. We implemented our approach and evaluated it on a set of benchmarks from the Simba paper. The experimental results showed that, on average, our approach reduces synthesis time to 74.2% of the original, without any loss in the quality.

Program Synthesis for JavaScript via Divide-and-Conquer and Abstraction Interpretation

Jungmin Jo, Hangyeol Cho, Woosuk Lee

http://doi.org/10.5626/JOK.2021.48.6.629

Program synthesis aims to automatically generate a program that satisfies the user intent expressed in the form of a high-level specification. Recent years have witnessed a surge in interest in applying this technology to a wide range of problems. Program synthesis can help improve software development productivity. In this paper, we present an algorithm for synthesizing Javascript programs from input-output examples. Our approach was based on a synergistic combination of the version space algebra-based approach, which can efficiently solve synthesis problems through divide-and-conquer, and abstract interpretation, which can be used to finitize infinite search spaces. We have implemented our approach and evaluated it in 140 problems of synthesizing string- and integer-manipulating programs. On average, the desirable programs were generated within nine seconds.


Search




Journal of KIISE

  • ISSN : 2383-630X(Print)
  • ISSN : 2383-6296(Electronic)
  • KCI Accredited Journal

Editorial Office

  • Tel. +82-2-588-9240
  • Fax. +82-2-521-1352
  • E-mail. chwoo@kiise.or.kr