A comparison of well-quasi orders on trees

TY - GEN

T1 - A comparison of well-quasi orders on trees

AU - Mogensen, Torben Ægidius

N1 - David A. Schmidt’s 60th Birthday Festschrift

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Computer Science - Programming Languages, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, E.1, F.2.2, F.3.2

U2 - 10.4204/EPTCS.129.3

DO - 10.4204/EPTCS.129.3

M3 - Article in proceedings

T3 - Electronic Proceedings in Theoretical Computer Science

SP - 30

EP - 40

BT - Semantics, Abstract Interpretation, and Reasoning about Programs

A2 - Banerjee, Anindya

A2 - Danvy, Olivier

A2 - Doh, Kyung-Goo

A2 - Hatcliff, John

ER -