A Comparison of Well-Quasi Orders on Trees

Autor:	Mogensen, Torben Æ.
Rok vydání:	2013
Předmět:	Computer Science - Programming Languages Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms E.1 F.2.2 F.3.2
Zdroj:	EPTCS 129, 2013, pp. 30-40
Druh dokumentu:	Working Paper
DOI:	10.4204/EPTCS.129.3
Popis:	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. Comment: In Proceedings Festschrift for Dave Schmidt, arXiv:1309.4557
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1309.5130 Zobrazit plný text záznamu View this record from Arxiv