Weights for total division orderings on strings. / Scott, Elizabeth.

In: Theoretical Computer Science, Vol. 135, No. 2, 1994, p. 345-359.

Research output: Contribution to journalArticle

Published

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 languageEnglish
Pages (from-to)345-359
JournalTheoretical Computer Science
Volume135
Issue number2
DOIs
Publication statusPublished - 1994
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 1177207