Top > JACIII > Converting Constraint Handling Rules to Equivalent Transformat ...

single-jc.php

JACIII Vol.10 No.3 pp. 339-348
doi: 10.20965/jaciii.2006.p0339
(2006)

Paper:

Views over last 60 days: 431

Converting Constraint Handling Rules to Equivalent Transformation Rules

Yoshinori Shigeta*, Kiyoshi Akama**, Hiroshi Mabuchi***,
and Hidekatsu Koike****

*SoC Research and Development Center, Toshiba Corporation, 580-1 Horikawa-cho, Saiwai-ku, Kawasaki 212-8520, Japan

**Division of Large-Scale Computational Systems, Information Initiative Center, Hokkaido University, Kita 11 Nishi 5, Kita-ku, Sapporo, Hokkaido 060-0811, Japan

***Faculty of Software and Information Science, Iwate Prefectural University, 152-52 Sugo, Takizawa, Iwate 020-0193, Japan

****Faculty of Social Information, Sapporo Gakuin University, 11-banchi Bunkyodai, Ebetsu, Hokkaido 060-8555, Japan

Received:
February 22, 2005
Accepted:
December 21, 2005
Published:
May 20, 2006
Creative Commons License
Keywords:
equivalent transformation rule, constraint handling rule
Abstract
We present a way to convert constraint handling rules (CHRs) to equivalent transformation rules (ETRs) and demonstrate the correctness of the conversion in equivalent transformation (ET) theory. In the ET computation model, computation is regarded as equivalent transformations of a description. A description is transformed successively by ETRs. Extensively used in the domain of first-order terms, the ET computation model has also been applied to knowledge processing in such data domains as RDF, UML, and XML. A CHR is a multiheaded guarded rule that rewrites constraints into simpler ones until they are solved. CHRs and ETRs are similar in syntax but they have completely different theoretical bases for the correctness of their computation. CHRs are based on the logical equivalence of logical formulas, while ETRs are based on the set equivalence of descriptions. We convert CHRs to rules used in the ET model and demonstrate converted rules to be correct ETRs, i.e., they preserve meanings of descriptions. We discuss correspondences and differences between CHRs and ETRs in theories, giving examples of correct ETRs that cannot be represented as CHRs.
Cite this article as:
Y. Shigeta, K. Akama, H. Mabuchi, and H. Koike, “Converting Constraint Handling Rules to Equivalent Transformation Rules,” J. Adv. Comput. Intell. Intell. Inform., Vol.10 No.3, pp. 339-348, 2006.
Data files:
References
  1. [1] J. W. Lloyd, “Foundations of Logic Programming,” Springer-Verlag, 1987.
  2. [2] J. Jaffar, et al., “The semantics of Constraint Logic Programs,” J. of Logic Programming, 37, pp. 1-46, 1998.
  3. [3] P. Hudak, “Conception, Evolution and Application of Functional Programming Languages,” ACM Computing Surveys, 21(3), pp. 359-411, 1989.
  4. [4] M. Hanus, “The Integration of Functions into Logic Programming: From Theory to Practice,” J. of Logic Programming, 19,20, pp. 583-628, 1994.
  5. [5] K. Akama, et al., “Program Synthesis Based on the Equivalent Transformation Computation Model,” Proc. of 12th International Workshop on Logic Based Program Development and Transformation (LOPSTR 2002), pp. 285-304, 2002.
  6. [6] K. Akama, et al., “A Theoretical Foundation of Program Synthesis by Equivalent Transformation,” Lecture Notes in Computer Science, 2244, pp. 131-139, Springer Verlag, 2001.
  7. [7] K. Akama, et al., “Equivalent Transformation for Member Constraints on Term Domain,” J. of Japanese Society for Artificial Intelligence, 13-2, pp. 274-282, 1998.
  8. [8] K. Akama, et al., “Semantics for Declarative Descriptions with Referential Constraints,” Proc. of International Conference on Computing and Information Technologies, pp. 405-410, 2001.
  9. [9] K. Akama, et al., “A Class of Rewriting Rules and Reverse Transformation for Rule-Based Equivalent Transformation,” Electronic Notes in Theoretical Computer Science, 59(4), pp. 1-16, 2001.
  10. [10] K. Akama, et al., “Equivalent Transformation by Safe Extension of Data Structures,” Perspectives of System Informatics, Lecture Notes in Computer Science, Vol.2244, pp. 140-148, Springer Verlag, 2001.
  11. [11] V. Wuwongse, et al., “XML Declarative Description: A Language for the Semantic Web,” IEEE Intelligent Systems, pp. 54-65, 2001.
  12. [12] K. Akama, et al., “Query Formulation and Evaluation for XML Databases,” Proc. of WITASI 2002, pp. 273-288, 2002.
  13. [13] T. Frühwirth, “Theory and Practice of Constraint Handling Rules,” J. of Logic Programming, 37, pp. 95-138, 1998.
  14. [14] C. Holzbaur, and T. W. Fruhwirth, “Compiling Constraint Handling Rules into Prolog with Attributed Variables,” Lecture Notes in Computer Science, Vol.1702, pp. 117-133, 1999.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 22, 2024