MONOTONE CONGRUENCE ALGORITHMS,
Abstract
Given an associative system in which each element is assigned a cost and in which an equivalence relation obtains between elements, it is often of interest to ask the question: what is the least costly word equivalent to a given word. The case in which the equivalence relation is a two-sided congruence relation is studied here, one example being the problem of optimizing a type of computer program. Such optimizing processes may be formalized as Markov normal algorithms. A general result concerning order relations on finite alphabets is established first. Then, the properties of a class of Markov normal algorithms are investigated. It is shown that each such algorithm must always terminate, and that every class of mutually equivalent algorithms contains a unique minimal algorithm which can be obtained by applying any algorithm of the class to itself. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1965
- Accession Number
- AD0625046
Entities
People
- Donald L. Richards
- Richard F. Arnold