Monotone congruence algorithms

Given an associative system in which each word 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 results 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