The classification of polynomial orderings on monadic terms

N Cropper, U Martin

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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, omega, omega (2) and omega (omega), 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 omega, omega (2) or omega (omega), although there exist reduction orderings on n letters of order type up to omega (omegan-1).

Original languageEnglish
Pages (from-to)197-226
Number of pages30
JournalApplicable Algebra in Engineering Communication and Computing
Volume12
Publication statusPublished - Jul 2001

Keywords

  • termination
  • term rewriting systems
  • ordinals
  • TERMINATION
  • STRINGS

Fingerprint

Dive into the research topics of 'The classification of polynomial orderings on monadic terms'. Together they form a unique fingerprint.

Cite this