  Recently, there has been an increasing interest in the bottom-up evaluation
of the semantics of logic programs with complex terms. The presence of function
symbols in the program may render the ground instantiation infinite, and
finiteness of models and termination of the evaluation procedure, in the
general case, are not guaranteed anymore. Since the program termination problem
is undecidable in the general case, several decidable criteria (called program
termination criteria) have been recently proposed. However, current conditions
are not able to identify even simple programs, whose bottom-up execution always
terminates. The paper introduces new decidable criteria for checking
termination of logic programs with function symbols under bottom-up evaluation,
by deeply analyzing the program structure. First, we analyze the propagation of
complex terms among arguments by means of the extended version of the argument
graph called propagation graph. The resulting criterion, called
Gamma-acyclicity, generalizes most of the decidable criteria proposed so far.
Next, we study how rules may activate each other and define a more powerful
criterion, called safety. This criterion uses the so-called safety function
able to analyze how rules may activate each other and how the presence of some
arguments in a rule limits its activation. We also study the application of the
proposed criteria to bound queries and show that the safety criterion is
well-suited to identify relevant classes of programs and bound queries.
Finally, we propose a hierarchy of classes of terminating programs, called
k-safety, where the k-safe class strictly includes the (k-1)-safe class. Note:
To appear in Theory and Practice of Logic Programming (TPLP).
