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 termination analysis is obtained by interpreting size-change constraints over a sufficiently large but finite non-negative integer domain. A Boolean k-bit modeling of size change graphs using binary decision diagrams leads to a concise representation. Experimental evaluation indicates that the 2-bit representation facilitates an efficient implementation which is guaranteed complete for our entire benchmark suite. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11693024_16 | ESOP |
Keywords | Field | DocType |
concise representation,constraint solver,size-change termination analysis,large set,2-bit representation,size change graph,size-change constraint,size-change termination problem,proving size change termination,size-change graph,binary decision diagram,termination analysis,programming paradigm | Boolean function,Constraint satisfaction,Programming paradigm,Computer science,Algorithm,Binary decision diagram,Theoretical computer science,Constraint satisfaction problem,Decidability,Termination analysis,Boolean algebra | Conference |
Volume | ISSN | ISBN |
3924 | 0302-9743 | 3-540-33095-X |
Citations | PageRank | References |
6 | 0.48 | 7 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Codish | 1 | 45 | 5.54 |
Vitaly Lagoon | 2 | 340 | 24.46 |
Peter Schachte | 3 | 256 | 22.76 |
Peter J. Stuckey | 4 | 4368 | 457.58 |
PJ Stuckey | 5 | 6 | 0.48 |