A COMPUTER TECHNIQUE USEFUL FOR SOME PROBLEMS IN THE PARTITIONING THEORY OF SEQUENTIAL MACHINES.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1966
- Accession Number
- AD0634920
Entities
People
- William J. Sacco
Organizations
- Ballistic Research Laboratory