TY - JOUR
T1 - A grammar-based approach to invertible programs
AU - Matsuda, Kazutaka
AU - Mu, Shin Cheng
AU - Hu, Zhenjiang
AU - Takeichi, Masato
N1 - Funding Information:
We would like to thank Robert Glück, Keisuke Nakano, Kazuhiro Inaba, and Akimasa Morihata for their valuable comments on an earlier version of the paper. We are also grateful to the anonymous reviewers who gave us helpful advice to improve the paper. This work is partially supported by the Japan Society for the Promotion of Science, Grant-in-Aid for JSPS Fellows 20·9584 and Grant-in-Aid for Scientific Research (A) 19200002, and the Grand-Challenging Project on “Linguistic Foundation for Bidirectional Model Transformation” from National Institute of Informatics.
Funding Information:
Acknowledgments. We would like to thank Robert Glück, Keisuke Nakano, Kazuhiro Inaba, and Akimasa Morihata for their valuable comments on an earlier version of the paper. We are also grateful to the anonymous reviewers who gave us helpful advice to improve the paper. This work is partially supported by the Japan Society for the Promotion of Science, Grant-in-Aid for JSPS Fellows 20 · 9584 and Grant-in-Aid for Scientific Research (A) 19200002, and the Grand-Challenging Project on “Linguistic Foundation for Bidirectional Model Transformation” from National Institute of Informatics.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2010.
PY - 2010
Y1 - 2010
N2 - Program inversion has many applications such as in the implementation of serialization/deserialization and in providing support for redo/undo, and has been studied by many researchers. However, little attention has been paid to two problems: how to characterize programs that are easy or hard to invert and whether, for each class of programs, efficient inverses can be obtained. In this paper, we propose an inversion framework that we call grammar-based inversion, where a program is associated with an unambiguous grammar describing the range of the program. The complexity of the grammar indicates how hard it is to invert the program, while the complexity is related to how efficient an inverse can be obtained.
AB - Program inversion has many applications such as in the implementation of serialization/deserialization and in providing support for redo/undo, and has been studied by many researchers. However, little attention has been paid to two problems: how to characterize programs that are easy or hard to invert and whether, for each class of programs, efficient inverses can be obtained. In this paper, we propose an inversion framework that we call grammar-based inversion, where a program is associated with an unambiguous grammar describing the range of the program. The complexity of the grammar indicates how hard it is to invert the program, while the complexity is related to how efficient an inverse can be obtained.
UR - http://www.scopus.com/inward/record.url?scp=85040930564&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85040930564&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-11957-6_24
DO - 10.1007/978-3-642-11957-6_24
M3 - Conference article
AN - SCOPUS:85040930564
SN - 0302-9743
VL - 6012 LNCS
SP - 448
EP - 467
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
T2 - 19th European Symposium on Programming, ESOP 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010
Y2 - 20 March 2010 through 28 March 2010
ER -