Accession Number:

AD0625046

Title:

MONOTONE CONGRUENCE ALGORITHMS,

Descriptive Note:

Corporate Author:

INFORMATION SYSTEMS LAB UNIV OF MICHIGAN ANN ARBOR

Personal Author(s):

• Arnold,Richard F.
• Richards,Donald L.

Report Date:

1965-04-01

Pagination or Media Count:

27.0

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