Paper:

# Constraint Solving Specializations for Equality on an Interval-Variable Domain

## Hiroshi Mabuchi^{*}, Kiyoshi Akama^{**}, Katsunori Miura^{***},

and Takahiko Ishikawa^{****}

^{*}Faculty of Software and Information Science, Iwate Prefectural University, Iwate, Japan

^{**}Information Initiative Center, Hokkaido University, Sapporo, Japan

^{***}Information Initiative Center, Hokkaido University, Sapporo, Japan

^{****}Faculty of Health and Welfare Science, Nayoro City University, Nayoro, Japan

In the equivalent transformation (ET) model, where computation is regarded as ET using rules that constitute a program, this paper develops a theory for equality-constraint solving which unification does in the theory of logic programming. This paper clarifies the relationship between Constraint Solving Specializations for Equality (CSSEs) and unifiers. The concept of CSSE can be used to solve equality constraint in a clause, and promotes component-based programming. An algorithm for finding CSSEs in the domain including interval variables is constructed by combining simpler ET rules. Termination and correctness of the algorithm is proven.

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.11, No.2, pp. 210-219, 2007.

- [1] K. Akama, Y. Shigeta, and E. Miyamoto, “Changing Knowledge Representation Systems by Expanding Specialization Systems,” Journal of the Japanese Society for Artificial Intelligence, Vol.13, No.1, pp. 131-138, 1998.
- [2] K. Akama, Y. Shigeta, and E. Miyamoto, “Correctness Proof for Equivalent Transformation of Equality Constraints on an Interval Variable Domain,” Technical Report of IEICE, SS98-33, pp. 23-30, 1998.
- [3] K. Akama, Y. Kawaguchi, and E. Miyamoto, “Equivalent Transformation for Equality Constraints on the Multiset Domain,” Journal of the Japanese Society for Artificial Intelligence, Vol.13, No.3, pp. 395-403, 1998.
- [4] K. Akama, Y. Shigeta, and E. Miyamoto, “Solving Logical Problems by Equivalent Transformation (1) –A Theoretical Foundation–,” Journal of the Japanese Society for Artificial Intelligence, Vol.13, No.6, pp. 928-935, 1998.
- [5] 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, No.6, pp. 944-952, 1998.
- [6] K. Akama, Y. Shigeta, and E. Miyamoto, “From Most General Unifiers to Constraint Solving Specializations for Equality,” Technical Report of IEICE, SS98-24, pp. 23-30, 1998.
- [7] K. Akama, Y. Shigeta, and E. Miyamoto, “Unfold Transformation of Declarative Programs,” Journal of the Information Processing Society of Japan: Programming, Vol.40, No.SIG 7, pp. 9-23 (PRO4), 1999.
- [8] P. Chippimolchai, K. Akama, T. Ishikawa, and V. Wuwongse, “Correct Computation with Multi-Head Rules in the Equivalent Transformation Framework,” Proc. of the 4th International Conference on Intelligent Technologies, pp. 531-538, 2003.
- [9] T. Frühwirth, “Theory and Practice of Constraint Handling Rules,” Journal of Logic Programming, Special Issue on Constraint Logic Programming, 37(1-3): pp. 95-138, 1998.
- [10] J. Jaffar and J.-L. Lassez, “Constraint Logic Programming,” Proc. 14th Ann. ACM Symp. Principles of Programming Languages, pp. 111-119, 1987.
- [11] J. Jaffar and M. Maher, “Constraint Logic Programming: A Survey,” Journal of Logic Programming, 19, 20: pp. 503-581, 1994.
- [12] H. Koike, K. Akama, and E. Boyd, “Program Synthesis by Generating Equivalent Transformation Rules,” Proc. of the Second International Conference on Intelligent Technologies, pp. 250-259, 2001.
- [13] J. W. Lloyd, “Foundations of Logic Programming,” Second edition, Springer-Verlag, 1987.
- [14] H. Mabuchi, K. Akama, Y. Shigeta, and H. Koike, “Equivalent Transformation of Member Constraints on Interval-Variable Domain,” Journal of the Japanese Society for Artificial Intelligence, Vol.17, No.1 C, pp. 23-31, 2002.
- [15] A. Pettorossi and M. Proietti, “Transformation of Logic Programs: Foundations and Techniques,” Journal of Logic Programming, 19, 20, pp. 261-320, 1994.
- [16] Y. Shigeta, K. Akama, and E. Miyamoto, “Specialization System and Regular Definite Clauses for the Term Domain Including Interval Variable,” Technical Report of IEICE, SS98-8, pp. 17-24, 1998.
- [17] H. Tamaki and T. Sato, “Unfold/fold Transformation of Logic Programs,” Proc. of 2nd ILPC, pp. 127-138, 1984.
- [18] P. van Hentenryck, “Constraint Satisfaction in Logic Programming,” The MIT Press, 1989.
- [19] V. Wuwongse, C. Anutariya, K. Akama, and E. Nantajeewarawat, “XML Declarative Description: A Language for the Semantic Web,” IEEE Intelligent Systems, pp. 54-65, 2001.

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