| Summary: | The recursive path ordering is an established and crucial tool in term
rewriting to prove termination. We revisit its presentation by means of some
simple rules on trees (or corresponding terms) equipped with a 'star' as
control symbol, signifying a command to make that tree (or term) smaller in the
order being defined. This leads to star games that are very convenient for
proving termination of many rewriting tasks. For instance, using already the
simplest star game on finite unlabeled trees, we obtain a very direct proof of
termination of the famous Hydra battle, direct in the sense that there is not
the usual mention of ordinals. We also include an alternative road to setting
up the star games, using a proof method of Buchholz, adapted by van Oostrom,
resulting in a quantitative version of the star as control symbol. We conclude
with a number of questions and future research directions.
|
|---|