Accession Number : AD0634920

Title :   A COMPUTER TECHNIQUE USEFUL FOR SOME PROBLEMS IN THE PARTITIONING THEORY OF SEQUENTIAL MACHINES.

Descriptive Note : Memorandum rept.,

Corporate Author : BALLISTIC RESEARCH LABS ABERDEEN PROVING GROUND MD

Personal Author(s) : SACCO, William J.

Report Date : MAR 1966

Pagination or Media Count : 16

Abstract : One of the most powerful theories to emerge in sequential machine theory in the last few years is partitioning theory, as developed principally by J. Hartmanis and R. Stearns. There exist several valuable concepts used in partitioning theory, such as the partition with substitution property, partition pairs, and systems-pairs. Partitioning theory enables one to consider the possibility of realizing a given sequential machine M from interconnected sets of smaller machines. Partitions oith substitution property, partition pairs, and systems-pairs play a dominant role in the study of machine decomposition. Methods for generating partitions with substitution property have been given by Hartmanis and F. Farr. This paper presents a computer technique which enables one to verify whether, (1) a partition possesses substitution property, (2) two partitions constitute a partition pair, and (3) two set systems constitute a systems-pair. (Author)

Descriptors :   (*COMBINATORIAL ANALYSIS, *AUTOMATA), THEORY, COMPUTER PROGRAMMING

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE