Abstract
In this paper we consider total division orderings on strings. We give a simple proof of the fact that for each such ordering ≻ there exists an essentially unique, nontrivial set of weights such that if the weight of u is greater than the weight of u≻u. It is known that all total division orderings on strings are rational, we prove a slightly stronger version of this result. Also, we use the ideas involved in the proof of the weights result to give a much simpler proof of the rationality result.
Original language | English |
---|---|
Pages (from-to) | 345-359 |
Journal | Theoretical Computer Science |
Volume | 135 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1994 |