
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 systemspairs. 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 systemspairs 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 systemspair. (Author)
Descriptors : (*COMBINATORIAL ANALYSIS, *AUTOMATA), THEORY, COMPUTER PROGRAMMING
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE