PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (11/30/87)
PROLOG Digest Tuesday, 1 Dec 1987 Volume 5 : Issue 94
Theory - Impediments,
Implementation - Chestnuts
----------------------------------------------------------------------
Date: 25 Nov 87 22:23:04 GMT
From: aramis.rutgers.edu!chomicki@rutgers.edu (Jan Chomicki)
Subject: Theoretical impediments to logic programming?
Rabin and Fischer's result about the inherent complexity of Presburger
arithmetic has no relevance for Prolog. In Prolog you can not write
most of the sentences of this arithmetic, because of the lack of:
- arbitrary quantification.
- equations, like y=x+x.
- propositional connectives 'not' and 'or'.
SLD-resolution (or for that matter any resolution method alone)
can not handle Presburger arithmetic. It is quite possible
that the arithmetic hacks (like is/2) with which we have to live
were born out of their designers' fear of the inherent complexity
(or even undecidability if both + and * are allowed) of arithmetic.
The complexity results relevant for Prolog can be found in papers about
the satisfiability problem for propositional and first order formulas
( Lewis 1980, Plaisted 1984: both in Journal of Computer and System
Sciences). And those results confirm a special role of Horn clauses.
For example, satisfiability of propositional Horn clauses is in P as
opposed to the general case which is NP-complete.
-- Jan Chomicki
------------------------------
Date: 26 Nov 1987 1707-WET (Thursday)
From: Jamie Andrews <jha%cstvax.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Subject: Narain's comments on Presburger and Logic Programming
Sanjay Narain enters an interesting area in his discussion of
Rabin's result about the structural complexity of Presburger
arithmetic. But let me first just correct some of his assumptions:
1. The Horn clausal calculus is _not_ richer than Presburger
arithmetic. PrA is a first-order theory, and thus has universal
quantifier and negation, which Horn clauses don't have.
(Though some may not realise this, the problems of getting
'forall' and 'not' into Prolog have not been solved.)
2. SLD-resolution is not a decision procedure, in the sense that
Rabin was probably using it, because it is not deterministic.
This is a kind of picky point, because I assume Sanjay meant
``the usual sequential implementation of SLD-resolution''
wherever he used the term.
Now we may be able to see why Prolog and similar systems escape
Rabin's net. They are not only not trying to solve PrA efficiently,
they are not trying to solve any first-order theory at all! They
are just trying to solve a subset of a first-order theory derived
from the program. The precise subset they are trying to solve is
something I'm working on finding.
I agree with Sanjay, though, that sequential logic programming
systems involve the notion of (sequential) algorithm in a way that
is hard to model in pure logic. This is quite a stumbling-block
in trying to apply pure logic to logic programming.
--Jamie.
------------------------------
Date: Wed, 25 Nov 87 13:16:11 CST
From: raghu@cs.wisc.edu (Raghu Ramakrishnan)
Subject: follow-up to a posting
This is being worked on by a lot of people in the database community.
For a survey and comparison of several strategies (mostly bottom-up,
but including Prolog) on a small set of programs including various
versions of transitive closure, see the paper by Bancilhon and
Ramakrishnan in SIGMOD 86, "An Amateur's Introduction to Recursive
Query Processing Strategies." The paper makes observations similar
to O'Keefe's regarding Prolog, and provides some numbers to go with them.
A revised version with more details about the performance comparisons
(to appear in a book edited by Minker, "Foundations of Logic Programming
and Deductive Databases") is also available, and you can get a copy from
me. (I'd appreciate your looking at the SIGMOD version first to see if
you're interested! :-))
-- Raghu Ramakrishnan
------------------------------
End of PROLOG Digest
********************