Formalization of the Equivalent Transformation Computation Model
Kiyoshi Akama*, and Ekawit Nantajeewarawat**
*Division of Large-Scale Computational Systems, Information Initiative Center, Hokkaido University, Kita 11 Nishi 5, Kita-ku, Sapporo, Hokkaido 060-0811, Japan
**Computer Science Program, Sirindhorn International Institute of Technology, Thammasat University, P.O. Box 22, Thammasat-Rangsit Post Office, Rangsit Campus, Pathumthani 12121, Thailand
In the equivalent transformation (ET) computation model, a specification provides background knowledge in a problem domain and defines a set of queries of interest. A program is a set of prioritized transformation rules, and computation consists in successive reduction of queries using meaning-preserving transformation with respect to given background knowledge. We present a formalization of the ET model from the viewpoint of program synthesis, where not only computation but also program correctness and correctness relations are of central importance. The notion of program correctness defines “what it means for a program to be correct with respect to a specification,” and a correctness relation provides guidance on “how to obtain such a program.” The correctness relation of the ET model is established, based on which how the basic structure of the ET model facilitates program synthesis is discussed together with program synthesis strategies in this model.
-  K. Akama, “Semantic Processing of Natural Language Sentences by Equivalent Transformation,” Hokkaido University Information Engineering Technical Report, HIER-LI-9225, 1992.
-  K. Akama, Y. Nomura, and E. Miyamoto, “Semantic Interpretation of Natural Language Descriptions by Program Transformation,” Computer Software, Vol.12, No.5, pp. 45-62, 1995.
-  C. Anutariya et al., “RDF Declarative Description (RDD): A Language for Metadata,” Journal of Digital Information, Vol.2, No.2, 2001.
-  E. Nantajeewarawat et al., “Toward Reasoning with Unified Modeling Language Diagrams Based-on Extensible Markup Language Declarative Description Theory,” International Journal of Intelligent Systems, Vol.19, pp. 89-98, 2004.
-  V. Wuwongse et al., “A Data Model for XML Databases,” Journal of Intelligent Information Systems, Vol.20, No.1, pp. 63-80, 2003.
-  K. Akama, T. Shimizu, and E. Miyamoto, “Solving Problems by Equivalent Transformation of Declarative Programs,” Journal of the Japanese Society for Artificial Intelligence, Vol.13, pp. 944-952, 1998.
-  K. Akama, E. Nantajeewarawat, and H. Koike, “A Class of Rewriting Rules and Reverse Transformation for Rule-Based Equivalent Transformation,” Electronic Notes in Theoretical Computer Science, Vol.59, No.4, pp. 1-16, 2001.
-  K. Akama, E. Nantajeewarawat, and H. Koike, “Program Synthesis Based on the Equivalent Transformation Computation Model,” in Proc. the 12th Intl. Workshop on Logic Based Program Synthesis and Transformation, Madrid, Spain, pp. 285-304, 2002.
-  J. W. Lloyd, “Foundations of Logic Programming,” second, extended edition, Springer-Verlag, 1987.
-  T. Frühwirth, “Theory and Practice of Constraint Handling Rules,” Journal of Logic Programming, Vol.37, pp. 95-138, 1998.
-  J. Jaffar et al., “The Semantics of Constraint Logic Programs,” Journal of Logic Programming, Vol.37, pp. 1-46, 1998.
-  P. Hudak, “Conception, Evolution and Application of Functional Programming Languages,” ACM Computing Surveys, Vol.21, No.3, pp. 359-411, 1989.
-  K. Akama, and E. Nantajeewarawat, “Formalization of Computation Models in View of Program Synthesis,” in Proc. the 4th Intl. Conference on Intelligent Technologies, Chiang Mai, Thailand, pp. 507-516, 2003.
-  A. Pettorossi, and M. Proietti, “Rules and Strategies for Transforming Functional and Logic Programs,” ACM Computing Surveys, Vol.28, No.2, pp. 360-414, 1996.
-  A. Pettorossi, and M. Proietti, “Transformation of Logic Programs,” in D. M. Gabbay, C. J. Hogger, and J. A. Robinson, Eds., Handbook of Logic in Artificial Intelligence and Logic Programming, Vol.5, Oxford University Press, pp. 697-787, 1998.
-  K. Akama, and E. Nantajeewarawat, “Computation Frameworks, Program Synthesis, and Correctness Relations,” Technical Report, Information Initiative Center, Hokkaido University, 2004.
-  J. Woodcock, and J. Davies, “Using Z Specification, Refinement and Proof,” Prentice Hall, 1996.
-  C. Morgan, “Programming from Specifications,” International Series in Computer Science, Prentice Hall, 1994.
-  J. M. Morris, “A Theoretical Basis for Stepwise Refinement and the Programming Calculus,” Science of Computer Programming, Vol.9, No.3, pp. 287-306, 1987.
-  N. Wirth, “Program Development by Stepwise Refinement,” Communications of the ACM, Vol.14, No.4, pp. 221-227, 1971.
-  Y. Gurevich, “Sequential Abstract-State Machines Capture Sequential Algorithms,” ACM Transactions on Computational Logic, Vol.1, No.1, pp. 77-111, 2000.
-  K. Akama, and E. Nantajeewarawat, “Formalization of the Constraint Logic Programming Computation Model,” Technical Report, Information Initiative Center, Hokkaido University, 2004.
-  H. Koike, K. Akama, and E. Boyd, “Program Synthesis by Generating Equivalent Transformation Rules,” in Proc. the 2nd Intl.Conference on Intelligent Technologies, Bangkok, Thailand, pp. 250-259, 2001.
-  I. Takarajima et al., “Design of Termination for Non-Deterministic Programs Based on the Equivalent Transformation Computation Model,” in Proc. the 5th Intl. Conference on Intelligent Technologies, Houston, Texas, pp. 226-235, 2004.