Publication details

Saarland University Computer Science

Smallest Horn Clause Programs

P. Devienne, P. Lebegue, A. Parrain, J.C. Routier, Jörg Würtz

Journal of Logic Programming 27(3):227-267, June 1996

The simplest non-trivial program pattern in logic programming is the following one : $$lefteginarrayl p( extitfact)leftarrow p( extitleft)leftarrow p( extitright). leftarrow p( extitgoal). endarray ight.defglobble#1gobble$$ where extitfact, extitgoal, extitleft and extitright are arbitrary terms. Because the well known extitappend program matches this pattern, we will denote such programs `` extitappend-like''.
In spite of their simple appearance, we prove in this paper that termination and satisfiability (i.e the existence of answer-substitutions, called the extitemptiness problem) for are undecidable. We also study some subcases depending on the number of occurrences of variables in extitfact, extitgoal, extitleft or extitright.
Moreover, we prove that the computational power of extitappend-like programs is equivalent to the one of Turing machines ; we show that there exists an extitappend-like universal program. Thus, we propose an equivalent of the Böhm-Jacopini theorem for logic programming. This result confirms the expressiveness of logic programming.
The proofs are based on program transformations and encoding of problems, unpredictable iterations within number theory defined by J.H. Conway or the Post correspondence problem.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009