Top > JACIII > Infinite Computation in the Equivalent Transformation Model

single-jc.php

JACIII Vol.11 No.2 pp. 176-186
doi: 10.20965/jaciii.2007.p0176
(2007)

Paper:

Views over last 60 days: 471

Infinite Computation in the Equivalent Transformation Model

Hiroshi Mabuchi*, Kiyoshi Akama**, Hidekatsu Koike***,
and Katsunori Miura**

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

**Information Initiative Center, Hokkaido University, Sapporo, Japan

***Faculty of Social Information, Sapporo Gakuin University, Ebetsu, Hokkaido, Japan

Received:
January 27, 2006
Accepted:
November 27, 2006
Published:
February 20, 2007
Creative Commons License
Keywords:
infinite computation, infinite term, greatest fixpoint, equivalent transformation
Abstract
There are many logic programs that do not terminate but perform useful computation in some sense. The usual theory of logic programming adopts least fixpoints to define the meaning of programs, which fails to capture the intended meaning of infinite computation. To give an appropriate sense to useful infinite computation, the theory of logic programming has adopted greatest fixpoints in place of least fixpoints. However, this solution developed in logic paradigm can not explain finite and infinite computation in a unified manner. This paper proposes a new approach to infinite computation based on the equivalent transformation paradigm, where infinite computation is regarded as repeated equivalent transformations and is given appropriate sense in the same way as the usual finite computation.
Cite this article as:
H. Mabuchi, K. Akama, H. Koike, and K. Miura, “Infinite Computation in the Equivalent Transformation Model,” J. Adv. Comput. Intell. Intell. Inform., Vol.11 No.2, pp. 176-186, 2007.
Data files:
References
  1. [1] M. A. Nait Abdallah, “On the Interpretation of Infinite Computatations in Logic Programming,” in 11th International Colloquium on Automata, Languages and Programming, ICALP’84, J. Paredaens (Ed.), pp. 358-370, Vol.172 of Lecture Notes in Computer Science, Springer-Verlag, 1984.
  2. [2] K. Akama, T. Shimizu, and E. Miyamoto, “Solving Problems by Equivalent Transformation of Declarative Programs,” Journal of Japanese Society for Artificial Intelligence, Vol.13, No.6, pp. 944-952, 1998.
  3. [3] K. Akama, Y. Shigeta, and E. Miyamoto, “Changing Knowledge Representation Systems by Expanding Specialization Systems,” Journal of Japanese Society for Artificial Intelligence, Vol.13, No.1, pp. 131-138, 1998.
  4. [4] K. Akama, Y. Kawaguchi, and E. Miyamoto, “Equivalent Transformation for Equality Constraints on Multiset Domains,” Journal of Japanese Society for Artificial Intelligence, Vol.13, No.3, pp. 395-403, 1998.
  5. [5] K. Akama, Y. Shigeta, and E. Miyamoto, “Solving Logical Problems by Equivalent Transformation (1) –A Theoretical Foundation–,” Journal of Japanese Society for Artificial Intelligence, Vol.13, No.6, pp. 928-935, 1998.
  6. [6] 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, 59, No.4, pp. 1-16, 2001.
  7. [7] K. R. Apt and van M. H. Emden, “Contributions to the Theory of Logic Programming,” JACM, Vol.29, No.3, pp. 841-862, 1982.
  8. [8] P. Boizumault, “A Classical Implementation for PrologII,” Lecture Notes in Computer Science, Vol.213, pp. 262-273, Springer-Verlag, 1986.
  9. [9] W. F. Clocksin and C. S. Mellish, “Programming in Prolog,” 2nd edition, Springer-Verlag, 1984.
  10. [10] A. Colmerauer, “Prolog and Infinite Trees,” Logic Programming, Academic Press, 1982.
  11. [11] F. S. de Boer, A. Di Pierro, and C. Palamidessi, “Nondeterminism and Infinite Computations in Constraint Programming,” Theoretical Computer Science, 151, pp. 37-78, 1995.
  12. [12] W. G. Golson, “Toward a Declarative Semantics for Infinite Objects in Logic Programming,” Journal of Logic Programming, 5, pp. 151-164, 1988.
  13. [13] J. Hein, “Completions of Perpetual Logic Programs,” Theoretical Computer Science, 99, pp. 65-78, 1992.
  14. [14] J. Jaffar and J. L. Lassez, “Constraint Logic Programming,” in Conference Record of the Fourteenth Annual ACMSymposium on Principles of Programming Languages, pp. 111-119, 1987.
  15. [15] G. Levi and C. Palamidessi, “Contributions to the Semantics of Logic Perpetual Processes,” Acta Informatica, 25(6): pp. 691-711, 1988.
  16. [16] J. W. Lloyd, “Foundations of Logic Programming,” 2nd edition, p. 212, Springer-Verlag, 1987.
  17. [17] H. Mabuchi, K. Akama, Y. Shigeta, and H. Koike, “Equivalent Transformation of Member Constraints on Interval-Variable Domain,” Journal of Japanese Society for Artificial Intelligence, Vol.17, No.1 C, pp. 23-31, 2002.
  18. [18] M. Jaume, “On Greatest Fixpoint Semantics of Logic Programming,” J. Logic and Computation, Vol.12, No.2, pp. 321-342, 2002.
  19. [19] S. Nystrom and B. Jonsson, “Indeterminate Concurrent Constraint Programming: A Fixpoint Semantics for Non-Terminating Computations,” in Logic Programming – Proceedings of the 1993 International Symposium, D. Miller (Ed.), pp. 335-352, The MIT Press, 1993.
  20. [20] V. A. Saraswat, M. C. Rinard, and P. Panangaden, “Semantic Foundations of Concurrent Constraint Programming,” in Conference Record of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, pp. 333-352, 1991.
  21. [21] D. A. Turner, “An Overview of Miranda,” SIGPLAN Notices, Vol.21, No.12, pp. 158-166, 1986.
  22. [22] T. Yoshida, K. Akama, and E. Miyamoto, “Representation and Computation Using First-order Logical Constraints,” Proc. of the 5th International Conference on Information Systems Analysis and Synthesis, 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