Conference Proceedings

Size-change termination analysis in kappa-bits

M Codish, V Lagoon, P Schachte, PJ Stuckey, P Sestoft (ed.)

PROGRAMMING LANGUAGES AND SYSTEMS, PROCEEDINGS | SPRINGER-VERLAG BERLIN | Published : 2006

Abstract

Size-change termination analysis is a simple and powerful technique successfully applied for a variety of programming paradigms. A main advantage is that termination for size-change graphs is decidable and based on simple linear ranking functions. A main disadvantage is that the size-change termination problem is PSPACE-complete. Proving size change termination may have to consider exponentially many size change graphs. This paper is concerned with the representation of large sets of size-change graphs. The approach is constraint based and the novelty is that sets of size-change graphs are represented as disjunctions of size-change constraints. A constraint solver to facilitate size-change t..

View full abstract