Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


On extra variables in (Equational) logic programming

Hanus, Michael

MPI-I-94-246. 1994, 33 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Extra variables in a clause are variables which occur in the body but not in the head. It has been argued that extra variables are necessary and contribute to the expressive power of logic languages. In the first part of this paper, we show that this is not true in general. For this purpose, we provide a simple syntactic transformation of each logic program into a logic program without extra variables. Moreover, we show a strong correspondence between the original and the transformed program with respect to the declarative and the operational semantics. In the second part of this paper, we use a similar technique to provide new completeness results for equational logic programs with extra variables. In equational logic programming it is well known that extra variables cause problems since narrowing, the standard operational semantics for equational logic programming, may become incomplete in the presence of extra variables. Since extra variables are useful from a programming point of view, we characterize
new classes of equational logic programs with extra variables for which narrowing and particular narrowing strategies are complete. In particular, we show the completeness of narrowing strategies in the presence of nonterminating functions and extra variables in right-hand sides of rewrite rules.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-94-246.pdfMPI-I-94-246.pdfMPI-I-94-246.dvi153 KBytes; 215 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Hanus, Michael},
  TITLE = {On extra variables in (Equational) logic programming},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-246},
  YEAR = {1994},
  ISSN = {0946-011X},