Torben Æ. Mogensen
(DIKU, University of Copenhagen, Denmark)
Well-quasi orders such as homeomorphic embedding are commonly used to ensure termination of program analysis and program transformation, in particular supercompilation.
We compare eight well-quasi orders on how discriminative they are and their computational complexity. The studied well-quasi orders comprise two very simple examples, two examples from literature on supercompilation and four new proposed by the author.
We also discuss combining several well-quasi orders to get well-quasi orders of higher discriminative power. This adds 19 more well-quasi orders to the list.
|ArXived at: http://dx.doi.org/10.4204/EPTCS.129.3||bibtex|
|Comments and questions to: email@example.com|
|For website issues: firstname.lastname@example.org|