The classification of polynomial orderings on monadic terms

We investigate, for the case of unary function symbols, polynomial ordering s on term algebras, that is reduction orderings determined by polynomial in terpretations of the function symbols. Any total reduction ordering over un ary function symbols can be characterised in terms of numerical invariants determined by the ordering alone: we show that for polynomial orderings the se invariants, and in some cases the ordering itself, are essentially deter mined by the degrees and leading coefficients of the polynomial interpretat ions. Hence any polynomial ordering has a much simpler description, and thu s the apparent complexity and variety of these orderings is less than it mi ght seem at first sight. In the case of two function symbols each of the three possible order types, omega, omega (2) and omega (omega), may be achieved by a polynomial orderi ng, 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 omega, omega (2) or omega (omega), although there exist reduction ord erings on n letters of order type up to omega (omegan-1).