Equivalence-preserving first-order unfold/fold transformation systems

AbstractTwo unfold/fold transformation systems for first-order programs, one basic and the other extended, are presented. The systems comprise an unfolding rule, a folding rule and a replacement rule. They are intended to work with a first-order theory Δ specifying the meaning of primitives, on top of which new relations are built by programs. They preserve the provability relationship Δ ∪ Γ ⊬ G between a call-consistent program Γ and a goal formula G such that Γ is strict with respect to G. They also preserve the logical consequence relationship in three-valued logic