The Classification of Polynomial Orderings on Monadic Terms

We investigate, for the case of unary function symbols, polynomial orderings on term algebras, that is reduction orderings determined by polynomial interpretations of the function symbols. Any total reduction ordering over unary function symbols can be characterised in terms of numerical invariants determined by the ordering alone: we show that for polynomial orderings these invariants, and in some cases the ordering itself, are essentially determined by the degrees and leading coefficients of the polynomial interpretations. Hence any polynomial ordering has a much simpler description, and thus the apparent complexity and variety of these orderings is less than it might seem at first sight. In the case of two function symbols each of the three possible order types, ω, ω² and ω^ω, may be achieved by a polynomial ordering, as may any permitted value of the invariants. For more function symbols polynomial orderings cease to have this universality as the order type is again ω, ω² or ω^ω, although there exist reduction orderings on n letters of order type up to ω^{ωn − 1}. Received: June 1, 1998; revised version: September 18, 1999