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 ?
- the depreciation rate used to calculate the expected valuation in the UK specific voluntary termination analysis has been widened to allow for a lower rate, reflecting the flattening observed in pools with more used cars
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.1, which is based on detecting when a rule's action may cause another rule's condition to become true.
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.
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.
At least on the level of automatic termination analysis, the current status of all this work can be evaluated as follows.
An essential component of any termination analysis framework is the ability of measuring and comparing atoms and terms.