Volume 7: January - December 1997

Issue 3: 1997


Regular search spaces and constructive negation

  • Regular search spaces and constructive negation
  • A. Momigliano1 and M. Ornaghi2

    1Department of Philosophy, Carnegie Mellon University, 15213 Pittsburgh PA, USA. E-mail: am4e@cmu.edu and 2Dipartimento di Scienze dell'Informazione, Universita' degli studi di Milano, Via Comelico 39/41, Milano, Italy. E-mail: ornaghi@imiucca.csi.unimi.it


    The aim of this paper is to show the fruitfulness and fecundity of the authors' proof-theoretic analysis of logic programming (both for definite and normal programs). It is based on a simple logical framework that goes under the name of regular search spaces. The challenge faced here is to give a treatment in proof-theoretic terms of the issue of negation, which has been one of the toughest problems that has plagued logic programming from its very beginning. While negation-as-failure (NF) has been overwhelmingly the more widespread answer, its intrinsic limitations have made it a rather unsatisfactory solution. In the present paper it is first contended that the notion of regularity offers a better understanding of the traditional theory of NF, and second a firm yet very simple and natural basis for a form of constructive negation, in the sense of Chan, Stuckey and Harland. A version of constructive negation is presented, based on the notion of regular splitting, a transformation technique where the failure axiom(s) of a predicate occurring negatively in a program are split into new clauses according to a covering of the underlying signature.

    Keywords: Logic programming, proof-theory, negation-as-failure, constructive negation, search spaces

    Pages: 367 - 403

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    Click here to register with OUP.

    This page is maintained by OUP admin

    Part of the OUP Journals World Wide Web service.

    Last modification: 22 Jul 1997

    Copyright© Oxford University Press, 1997.