Abstract

In this paper we extend the lazy narrowing calculus of Middeldorp, Okui, and Ida (*) to conditional rewrite systems. We show that our calculus is strongly complete whenever basic conditional narrowing is complete. This generalizes one of the three main results of (*) to the conditional case. As a corollary we obtain the strong completeness for three classes of conditional rewrite systems, one of which is the class of decreasing and confluent systems. For this latter class we present a simple direct proof.

BibTeX Entry

@inproceedings{HM-FLOPS96,
 author    = "Mohamed Hamada and Aart Middeldorp",
 title     = "Strong Completeness of a Lazy Conditional Narrowing
              Calculus",
 booktitle = "Proceedings of the 2nd Fuji International Workshop on
              Functional and Logic Programming",
 publisher = "World Scientific",
 pages     = "14--32",
 year      = 1997
}