An Algorithm for Local Variable Elimination in Normal Logic Programs

A variable is local if it occurs in a clause body but not in its head. Local variables appear naturally in practical logic programming, but they complicate several aspects such as negation, compilation, memoization, static analysis, program approximation by neural networks etc. As a consequence, the absence of local variables yields better performance of several tools and is a prerequisite for many technical results. In this paper, we introduce an algorithm that eliminates local variables from a wide proper subclass of normal logic programs. The proposed transformation preserves the Clark-Kunen semantics for normal logic programs.