
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 twosided 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