Abstract | ||
---|---|---|
Size-change termination (SCT) is a general criterion to identify recursive function definitions that are guaranteed to terminate. It extends and subsumes the simpler criterion of lexicographic descent in function calls, which in classical recursion theory is known as multiple recursion . Neil Jones has conjectured that the class of functions computable by size-change terminating programs coincides with the multiply-recursive functions. This paper proves so. |
Year | Venue | Keywords |
---|---|---|
2002 | The Essence of Computation | general size-change termination,functions computable,size-change termination,simpler criterion,classical recursion theory,general criterion,multiple recursion,lexicographic descent,neil jones,multiply-recursive function,function call,recursive function definition,recursion theory |
Field | DocType | Volume |
Discrete mathematics,Source function,Computability theory,Mutual recursion,Lexicographical order,Double recursion,Recursive functions,Mathematics,Recursion,Computational complexity theory | Conference | 2566 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-00326-6 | 8 |
PageRank | References | Authors |
0.49 | 2 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amir M Ben-Amram | 1 | 327 | 30.52 |