This paper discusses the relationships of two important program classes of linearly recursive programs, that is, decomposable programs and rule commutative programs. We prove that the decomposable programs are always rule commutative. Furthermore, the rule commutative programs that satisfy certain conditions are decomposable. These results are meaningful for integrating the related specified optimization algorithms.

Program transformation is a kind of optimization techniques for logic programs, which aims at transforming equally a program into an other form by exploiting some properties or information of the program, so as to make the program cheaper to evaluate. In this paper, a new kind of property of logic programs, called reducibility, is exploited in program transformation. A recursive predicate is reducible if the values of some variables in the recursive predicate are independent to the remainder part and can be detached from the predicate after finite times of expansions. After being proved that the semantic notion of reducibility can be replaced by the syntactic notion of disconnectivity of a R-graph, which is a kind of graph model to represent the behavior of formula expansions, an efficient testing and factoring algorithm is proposed. The paper also extends some existed results on compiled formulas of linear sirups, and compares with some related work.