termination analysis


Also found in: Wikipedia.

termination analysis

A program analysis which attempts to determine whether evaluation of a given expression will definitely terminate.

Evaluation of a constant is bound to terminate, as is evaluation of a non-recursive function applied to arguments which are either not evaluated or which can themselves be proved to terminate. A recursive function can be shown to terminate if it can be shown that the arguments of the recursive calls are bound to reach some value at which the recursion will cease.

Termination analysis can never guarantee to give the correct answer because this would be equivalent to solving the halting problem so the answer it gives is either "definitely terminates" or "don't know".
Mentioned in ?
References in periodicals archive ?
A sampling of topics: communicating mathematics via pen-based interfaces, non-well-founded probabilities and coinductive probability logic, abstract matrix arithmetic, grammar- based automatic extraction of definitions, coverability problems for jumping petri nets, analytic approximate periodic solutions based on harmonic analysis, semi-automated wrappers using rule trees, dynamics of a utility based distributed video proxy-cache, termination analysis by program inversion, consideration on using ontologies in complex systems, bandwidth reservation and admission control, and data flow entropy collector.
1995b] describe a technique to improve runtime termination analysis.
This observation leads to our new technique for termination analysis presented in Section 5.
Termination analysis for CA rules is based on the notion of rule activation.
Hence, the core of termination analysis is determining when an edge should be included in the graph, that is, when one rule may activate another rule.
Hence, we propose a "mixed" termination analysis technique that exploits the stronger method provided by the propagation algorithm for quasi-CA rules and degenerates to the weaker event-action technique for ECA rules that are not quasi-CA.
j] exactly as we have done for termination analysis.
As we see it, the norm or level mapping-based approach to termination analysis for logic programs has gone through a number of research stages.
These works have been crucial for the entire development of the termination analysis area.
At the least, they were less targeted at gaining conceptual insight into the termination problem as a whole, at clarifying the importance of certain subproblems, and at providing conceptually clear frameworks for studying the different trade-offs in termination analysis in general.
1991; 1992], studied the problem from a more mathematical perspective, providing more insight into the various components of a termination analysis proof.
the inference of appropriate models, in automatic termination analysis often referred to as the inference of interargument or size relations over the selected norm,