FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS
Alfons Geser, Dieter Hofbauer, Johannes Waldmann, Hans Zantema · International Journal of Foundations of Computer Science · 2005
We present a technique based on the construction of finite automata to prove termination of string rewriting systems. Using this technique the tools Matchbox and TORPA are able to prove termination of particular string rewriting systems completely automatically for which termination was considered to be very hard until recently.