Consider the following statement that appeared in Lee's Ranking functions for size-change termination.

Let $G$ satisfy the SCT condition.

There is an effective procedure to construct a $G$-ranking function expressed using only min, max and lexicographic tuples of program parameters and constants.

I'm interested mostly in the computational side of it. Has this been implemented before? If so in which systems?

In fact, Lee's preliminar algorithm was made more practical by subsequent revisions in joint work with Ben-Amram and Codish. There remains the question of whether their claim complexity is aceptable in current verifiers and whether it has been tested in practice yet.

up vote 4 down vote accepted

The complexity is acceptable in current verifiers, and has been implemented in at least the AProVE termination analysis tool for term rewrite systems.

They describe their implementation in Lazy Abstraction for Size-Change Termination, by Codish, Fuhs, Giesl & Schneider-Kamp, basing their implementation on the papers you refer to. Performance is good both from an expressiveness point of view and a run-time perspective.

The additional (clever!) trick is to pre-process the search for an appropriate abstraction and ranking function into a SAT problem (along with other search procedures for termination analysis) and having a SAT solver try to simultaneously find an instance. This trick is common in the termination analysis community.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.