Accession Number : AD0625046

Title :   MONOTONE CONGRUENCE ALGORITHMS,

Corporate Author : INFORMATION SYSTEMS LAB UNIV OF MICHIGAN ANN ARBOR

Personal Author(s) : Arnold,Richard F. ; Richards,Donald L.

Report Date : APR 1965

Pagination or Media Count : 27

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)

Descriptors :   (*ALGORITHMS, COMPUTER PROGRAMMING), (*COMPUTER PROGRAMMING, OPTIMIZATION), AUTOMATA, SET THEORY, STATISTICAL PROCESSES

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE