Inferring Program Extensions from Traces

Roman Manevich, Sharon Shoham
Proceedings of The 14th International Conference on Grammatical Inference 2018, PMLR 93:139-154, 2019.

Abstract

We present an algorithm for learning a non-trivial class of imperative programs. The algorithm accepts positive traces—input stores followed by a sequence of commands—and returns a program that extends the target program. That is, it behaves the same as the target program on all valid inputs—inputs for which the target program successfully terminates, and may behave arbitrarily on other inputs. Our algorithm is based on a quotient construction of the control flow graph of the target program. Since not all programs have a quotient in a convenient form, the ability to infer an extension of the target program increases the class of inferred programs. We have implemented our algorithm and applied it successfully to learn a variety of programs that operate over linked data structures and integer arithmetic.

Cite this Paper

BibTeX
@InProceedings{pmlr-v93-manevich19a, title = {Inferring Program Extensions from Traces}, author = {Manevich, Roman and Shoham, Sharon}, booktitle = {Proceedings of The 14th International Conference on Grammatical Inference 2018}, pages = {139--154}, year = {2019}, editor = {Unold, Olgierd and Dyrka, Witold and Wieczorek, Wojciech}, volume = {93}, series = {Proceedings of Machine Learning Research}, month = {feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v93/manevich19a/manevich19a.pdf}, url = {https://proceedings.mlr.press/v93/manevich19a.html}, abstract = {We present an algorithm for learning a non-trivial class of imperative programs. The algorithm accepts positive traces—input stores followed by a sequence of commands—and returns a program that extends the target program. That is, it behaves the same as the target program on all valid inputs—inputs for which the target program successfully terminates, and may behave arbitrarily on other inputs. Our algorithm is based on a quotient construction of the control flow graph of the target program. Since not all programs have a quotient in a convenient form, the ability to infer an extension of the target program increases the class of inferred programs. We have implemented our algorithm and applied it successfully to learn a variety of programs that operate over linked data structures and integer arithmetic.} }
Endnote
%0 Conference Paper %T Inferring Program Extensions from Traces %A Roman Manevich %A Sharon Shoham %B Proceedings of The 14th International Conference on Grammatical Inference 2018 %C Proceedings of Machine Learning Research %D 2019 %E Olgierd Unold %E Witold Dyrka %E Wojciech Wieczorek %F pmlr-v93-manevich19a %I PMLR %P 139--154 %U https://proceedings.mlr.press/v93/manevich19a.html %V 93 %X We present an algorithm for learning a non-trivial class of imperative programs. The algorithm accepts positive traces—input stores followed by a sequence of commands—and returns a program that extends the target program. That is, it behaves the same as the target program on all valid inputs—inputs for which the target program successfully terminates, and may behave arbitrarily on other inputs. Our algorithm is based on a quotient construction of the control flow graph of the target program. Since not all programs have a quotient in a convenient form, the ability to infer an extension of the target program increases the class of inferred programs. We have implemented our algorithm and applied it successfully to learn a variety of programs that operate over linked data structures and integer arithmetic.
APA
Manevich, R. & Shoham, S.. (2019). Inferring Program Extensions from Traces. Proceedings of The 14th International Conference on Grammatical Inference 2018, in Proceedings of Machine Learning Research 93:139-154 Available from https://proceedings.mlr.press/v93/manevich19a.html.

Related Material