The Classification of Polynomial Orderings on Monadic Terms

Nick Cropper, Ursula Martin

Research output: Contribution to journalArticlepeer-review

Abstract

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, ω, ω2 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 ω, ω2 or ωω, although there exist reduction orderings on n letters of order type up to ωωn − 1.
Original languageEnglish
Pages (from-to)197-226
Number of pages30
JournalApplicable Algebra in Engineering, Communication and Computing
Volume12
Issue number3
DOIs
Publication statusPublished - 2001

Fingerprint

Dive into the research topics of 'The Classification of Polynomial Orderings on Monadic Terms'. Together they form a unique fingerprint.

Cite this