Search

The fundamentals of Post algebras are presented along with extensions that will be useful in a proposed multi-valued switching theory. A detailed examination of Post and Boolean functions is presented along with a functional representation that facilitates the comparison of Post and Boolean algebras. It is shown that Boolean functions of one variable can be represented as Post functions. The general relationships between Post and Boolean algebras are examined. The structure of Boolean subalgebras of Post algebras is discussed, with particular emphasis placed on algebras which are composed of Boolean and Post functions. A transformation between sets of Boolean functions and Boolean algebras of vectors is presented along with a further transformation from the Boolean algebras of vectors to sets of Post functions. The structure of equivalence classes of Post functions and their relationship to Boolean functions is examined. (Author)

The research was concerned with non-binary switching theory and its possible technical applications. The report summarizes the three main areas of research, namely: (1) multi-valued cellular cascades; (2) multi-valued feedback shift registers, and (3) design of an arithmetic unit using the symmetric ternary number representation. A list of publications prepared under the grant is given.

It is the object of this report to initiate a theory of logical design for networks in which information is not constrained to flow in only one direction along a connection between devices. A linear graph model is proposed for a very general class of such nets. A method of analysis based on this model is proposed for learning the state behavior of nets, and a canonical form for any net proposed. It is demonstrated that, under very general assumptions, any net of this kind must proceed from any initial state to an equilibrium state, and a bound is given on the number of vertex state changes which can take place in such a transition. Results are presented which describe the character of the stable states of such nets and place bounds on the number of such states. (Author), Doctoral Thesis.

Computer oriented algorithms for several laborious computations frequently encountered in switching theory and logic design are presented. They are algorithms for the computation of designation numbers, functional composition, detection of relations between Boolean functions, symbolic expansion of Boolean expressions, and approximate minimization of Boolean functions. These algorithms are useful in the construction of man/machine interactive systems for logic design automation. Machine independence and modularity are emphasized in the development of these algorithms. They have been programmed on the LINC computer., Sponsored in part by Grant PHS-RR-00396.

MMING, COMPUTER LOGICAUTOMATA, *SEQUENTIAL MACHINES, SWITCHING THEORY, FAULT TOLERANT COMPUTING, *FAULT DETECTIONThe report treats the problem of devising fault-detection experiments for sequential machines having their decompositions known. In these experiments inputs are applied at the input terminals of the machine and the outputs observed at the output terminals, and no intermediate terminal is accessible. The output at any intermediate terminal is assumed known only for the design of the test but is never used in the actual experiment. The problem is treated from the standpoint of machine identification, with a possible faulty machine being identified as either isomorphic to its faultfree counterpart or not isomorphic to it. A test for a component machine is designed such that all the states of the component are identified and also sufficient non-elementary transitions are identified for unique representation of the machine. (Modified author abstract)

Several classes of graphs defined on arbitrary n-dimensional (0,1) arrays are introduced. These classes of graphs have as their point set the set of 1's of the array. Different classes are distinguished by the manner in which adjacency is defined. Characterizations are obtained for all these classes of graphs. Let G be a graph. The classes of graphs defined on the adjacency, incidence, and clique-vertex matrices are related to properties of G. A new method of representing graphs is introduced. The points of the graph are represented by ordered n-tuples of integrers and two n-tuples are adjacent whenever they agree on one or more coordinates. Some of the applications of these classes of graphs include the consecutive 1's property of (0,1) matrices, switching theory minimization, circulant matrices, latin squares, a representation theory for directed graphs, and a graphical decomposition of automata. (Author), Report on the Theory and Applications of Automation Theory.