DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# Accession Number:

## AD0625046

# Title:

## MONOTONE CONGRUENCE ALGORITHMS,

# Descriptive Note:

# Corporate Author:

## INFORMATION SYSTEMS LAB UNIV OF MICHIGAN ANN ARBOR

# 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

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#