THINGS TO KNOW WHEN IMPLEMENTING LPO
Bernd Löchner · International Journal of Artificial Intelligence Tools · 2006
The Lexicographic Path Ordering (LPO) poses an interesting problem to the implementor: How to achieve a version that is both efficient and correct? The method of program transformation helps us to develop an efficient version step-by-step, making clear the essential ideas, while retaining correctness. By theoretical analysis we show that the worst-case behavior is thereby changed from exponential to polynomial. Detailed measurements show the practical improvements of the different variants. They allow us to assess experimentally various optimizations suggested for LPO.