A Generalization of the Folding Rule for the Clark-Kunen Semantics | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Generalization of the Folding Rule for the Clark-Kunen Semantics

  • Conference paper
Functional and Logic Programming (FLOPS 2008)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 4989))

Included in the following conference series:

  • 363 Accesses

Abstract

In this paper, we propose more flexible applicability conditions for the folding rule that increase the power of existing unfold/fold systems for normal logic programs. Our generalized folding rule enables new transformation sequences that, in particular, are suitable for recursion introduction and local variable elimination. We provide some illustrative examples and give a detailed proof of correctness w.r.t. the Clark-Kunen semantics.

This work has been partially supported by Spanish Project TIN2004-079250-C03-03.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Álvez, J., Lucio, P.: A generalization of the folding rule for the clark-kunen semantics. Technical Report UPV-EHU/LSI/TR 01-2008, Dept. of Languages and Information Systems. Basque Country University (January, 2008)

    Google Scholar 

  2. Álvez, J., Lucio, P., Orejas, F., Pasarella, E., Pino, E.: Constructive negation by bottom-up computation of literal answers. In: Haddad, H., Omicini, A., Wainwright, R.L., Liebrock, L.M. (eds.) Proceedings of the 2004 ACM Symposium on Applied Computing (SAC), pp. 1468–1475 (2004)

    Google Scholar 

  3. Apt, K.R.: Logic programming. In: Handbook of Theoretical Computer Science. Formal Models and Sematics (B), vol. B, pp. 493–574. Elsevier, Amsterdam (1990)

    Google Scholar 

  4. Barbuti, R., Mancarella, P., Pedreschi, D., Turini, F.: A transformational approach to negation in logic programming. J. Log. Program. 8(3), 201–228 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bossi, A., Cocco, N., Etalle, S.: Simultaneous replacement in normal programs. J. Log. Comput. 6(1), 79–120 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bossi, A., Etalle, S.: More on unfold/fold transformations of normal programs: Preservation of fitting’s semantics. In: Fribourg, L., Turini, F. (eds.) LOPSTR 1994 and META 1994. LNCS, vol. 883, pp. 311–331. Springer, Heidelberg (1994)

    Google Scholar 

  7. Burstall, R.M., Darlington, J.: A transformation system for developing recursive programs. J. ACM 24(1), 44–67 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  8. Chan, D.: Constructive negation based on the completed database. In: Kowalski, R.A., Bowen, K.A. (eds.) Proceedings of the Fifth International Conference and Symposium on Logic Programming, pp. 111–125. MIT Press, Cambridge (1988)

    Google Scholar 

  9. Clark, K.L.: Negation as failure. In: Gallaire, H., Minker, J. (eds.) Logic and Data Bases, pp. 293–322. Plenum Press (1978)

    Google Scholar 

  10. Comon, H., Lescanne, P.: Equational problems and disunification. J. Symb. Comput. 7(3/4), 371–425 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  11. Debray, S.K., López-García, P., Hermenegildo, M.V.: Non-failure analysis for logic programs. In: Naish, L. (ed.) Logic Programming. Proceedings of the Fourteenth International Conference on Logic Programming, Leuven, Belgium, July 8-11, 1997, pp. 48–62. MIT Press, Cambridge (1997)

    Google Scholar 

  12. Dix, J.: A classification theory of semantics of normal logic programs: II. weak properties. Fundam. Inform. 22(3), 257–288 (1995)

    MATH  MathSciNet  Google Scholar 

  13. Gardner, P.A., Shepherdson, J.C.: Unfold/fold transformations of logic programs. In: Computational Logic - Essays in Honor of Alan Robinson, pp. 565–583 (1991)

    Google Scholar 

  14. Van Gelder, A., Ross, K., Schlipf, J.S.: Unfounded sets and well-founded semantics for general logic programs. In: PODS 1988: Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pp. 221–230. ACM Press, New York, NY, USA (1988)

    Chapter  Google Scholar 

  15. Gergatsoulis, M., Katzouraki, M.: Unfold/fold transformations for definite clause programs. In: Penjam, J. (ed.) PLILP 1994. LNCS, vol. 844, pp. 340–354. Springer, Heidelberg (1994)

    Google Scholar 

  16. Kanamori, T., Fujita, H.: Unfold/fold transformation of logic programs with counters. Technical Report TR-179, ICOT Institute for New Generation Computer Technology (1986)

    Google Scholar 

  17. Kowalski, R.A.: Predicate logic as programming language. In: IFIP Congress, pp. 569–574 (1974)

    Google Scholar 

  18. Kunen, K.: Negation in logic programming. J. Log. Program. 4(4), 289–308 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  19. Lloyd, J.W.: Foundations of Logic Programming, 2nd edn. Springer, Berlin (1987)

    MATH  Google Scholar 

  20. Lucio, P., Orejas, F., Pino, E.: An algebraic framework for the definition of compositional semantics of normal logic programs. J. Log. Program. 40(1), 89–124 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  21. Maher, M.J.: Correctness of a logic program transformation system. Technical Report RC 13496, IBM T.J. Watson Research Center (1988)

    Google Scholar 

  22. Maher, M.J.: A tranformation system for deductive databases modules with perfect model semantics. Theor. Comput. Sci. 110(2), 377–403 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  23. Pettorossi, A., Proietti, M.: Transformation of logic programs. In: Gabbayand, D.M., Hogger, C.J., Robinson, J.A. (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 6, pp. 697–787. Oxford University Press, Oxford (1998)

    Google Scholar 

  24. Roychoudhury, A., Kumar, K.N., Ramakrishnan, C.R., Ramakrishnan, I.V.: Beyond tamaki-sato style unfold/fold transformations for normal logic programs. Int. J. Found. Comput. Sci. 13(3), 387–403 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  25. Sato, T.: Equivalence-preserving first-order unfold/fold transformation systems. Theor. Comput. Sci. 105(1), 57–84 (1992)

    Article  MATH  Google Scholar 

  26. Sato, T., Tamaki, H.: Transformational logic program synthesis. In: Proceedings of the International Conference on Fifth Generation Computer Systems, pp. 195–201 (1984)

    Google Scholar 

  27. Seki, H.: Unfold/fold transformations of stratified programs. Theor. Comput. Sci. 86(1), 107–139 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  28. Seki, H.: Unfold/fold transformation of general logic programs for the well-founded semantics. J. Log. Program. 16(1), 5–23 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  29. Tamaki, H., Sato, T.: Unfold/fold transformation of logic programs. In: Tärnlund, S.-Å. (ed.) Proceedings of the Second International Logic Programming Conference, Uppsala University, Uppsala, Sweden, pp. 127–138 (1984)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Basque Country University,  

    Javier Álvez & Paqui Lucio

Authors
  1. Javier Álvez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paqui Lucio
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jacques Garrigue Manuel V. Hermenegildo

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Álvez, J., Lucio, P. (2008). A Generalization of the Folding Rule for the Clark-Kunen Semantics. In: Garrigue, J., Hermenegildo, M.V. (eds) Functional and Logic Programming. FLOPS 2008. Lecture Notes in Computer Science, vol 4989. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78969-7_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78969-7_14

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78968-0

  • Online ISBN: 978-3-540-78969-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation