article
article
Certain properties of three variants of the multi-tape automata of Rabin and Scott are proved. Closure properties of the defined sets of n-tuples are found, and the nature of projections of the defined sets of n-tuples on one coordinate is studied. Some necessary conditions for acceptance are derived, and a characterization of the sets of n-tuples defined by non-deterministic n-tape automata is found...
article
article
article
A diagrammatic approach to the problem of synthesizing multi-level logic functions is presented. It has the advantage of giving a visual interpretation to such abstract concepts as fan-in, levels of logic, decomposition, and two-level forms.
article
In this note we show how to construct some simply-configured N-state binary Turing machines that will start on a blank tape and eventually halt after printing a very large number of ones. The number of ones produced by these machines can be expressed analytically in terms of functional difference equation. The latter expression furnishes the best lower bound presently known for Rado's noncomputable...
article
This paper presents an extension of the basic concepts established by Robert McNaughton and David Muller in the field of asynchronous feedback networks. The ideas developed herein are the results of adapting common logical functions in a manner that simplifies the overall design of asynchronous systems. The prime objecttive is to overcome a weakness common to both of the aforementioned concepts, that...
article
article
This paper describes the design of experimental procedures for determining whether or not a sequential switching circuit is operating in accordance with a given state-table description. These procedures are particularly easy to apply when the given state table is reduced, strongly-connected, and has a distinguishing sequence, and when the actual circuit has no more states than the given table. They...
article
In this paper we investigate how numbers, functions, and sequences can be classified according to their computational complexity. The computational complexity is measured by how fast the number or function can be computed by a multitape computer (Turing machine). It is shown that by means of this measure the computational complexity of numbers and functions can be submitted to rigorous mathematical...
article
Closed form expressions are obtained for enumerating the non-equivalent finite automata under serveral definitions of equivalence. Algorithms are presented for determining the number of connected automata and automata with a distinguished initial state. Useful lower bounds and asymptotic results are obtained.
article
article
This paper presents several uses of the logical connective of implication to problems of interest in switching theory. The implications which hold among the prime implicants of a function are examined. A new set of necessary and sufficient conditions for determining essential prime implicants and a rapid approximate method for obtaining minimal sums are included.
article
In this paper, we define and discuss generalizations of partition pairs on sequential machines. The object of these generalizations is to suggest a unified approach to problems of information flow and machine structure.
article
Solving prime implicant tables is greatly facilitated by reduction techniques such as row dominance, column dominance and essential row selection. This paper presents a new reduction technique which is operable on any otherwise irreducible table having a column covered by two rows.
article
In this paper a method is presented for reducing the number of stages of logic in the realization of an arbitrary Boolean function when an upper bound exists on the fan-in at each gate. A procedure for obtaining the minimum stage realization of the function in sum of products form is first developed. The use of factoring to reduce the number of stages below this minimum is then described.
article
A technique is presented for deriving the shortest sequence of input symbols which must be applied to a sequential machine to guarantee that no fault from a set {p} exists within the machine. Flow tables are used to describe the machine for which a test is desired as well as all defective machines into which it is transformed by the faults of {p}. The set of flow tables is combined into a single composite...
article
Consideration is given to the manner and extent to which propagation delay and terminal packing factors may constrain the interconnection of modules making up large digital network. When formulated in graph-theoretical terms these considerations give rise to the problem of finding linear graphs with a maximum number, n, of nodes for a given degree, d, and diameter, k--a generalization of the problem...
article
A speed independent circuit has the property that the relative speed of operation of the various logic elements does not affect the over-all behavior of the circuit. Such circuits have properties which are of particular importance in the design of reliable asynchronous circuits. An Arithmetic Control for a digital computer is one type of logic which can profitably use these characteristics. The design...
article
