R70-43 Lattice Functions, Pair Algebras, and Finite-State Machines
This paper is yet another solution for finding linear internal state assignments for the next-state behavior of a sequential machine. A state assignment is said to be linear if and only if the resulting next-state variables are linear combinations ofthe present-state and input variables. Consequently, the next-state behavior of a sequential machine is said to be linear if and only if there exists a one-to-one assignment which is linear. The problem of finding linear assignments has received considerable attention, probably due to their inherent mathematical structure, and hopefully to further illuminate the theory of sequential machines in general. The prime contribution of this paper is a refinement of a previously presented algorithm [1] for finding linear assignments. In this algorithm an assignment is found for a single column, as an autonomous machine, and it is then checked for validity with the remaining columns. The problem, of course, is to be able to restrict the choice of possible assignments so that the number that has to be checked for validity is sufficiently small to keep the process from becoming an exhaustive search. This the author has managed to do, with reasonable success. The author does go into considerable detail in explaining the background and individual steps of the algorithm. While all of the detail may be useful, it does make the paper significantly longer than it needs to be. The prime criticism of the paper is not in the algorithm itself, but in what the author purports that it will do. In the first instance, it is stated that the algorithm is very effective even when the number of states is large. If the matrix A is not unique, then it is necessary to try each possible A in the subsequent steps of the algorithm. In such circumstances, an algorithm can hardly be termed effective. Furthermore, the method requires the graph of the matrix A, which is no easy task for large n (the order of A). As an example, if the cycle length is 19, then the order ofA is 18 and the graph contains 218 = 262 144 vectors of length 18, and yet a next-state table with 19 states is not at all unreasonable. It is therefore concluded that while the algorithm will work, it may become exceedingly tedious for some cases. In the second instance, the author restricts his algorithm to a realization oforder n, where the number of states is q, and 2n' < q< 2'. As an example, the following machine (machine l) has ten states and hence, following the author, n= 4. In contradiction, however, when the algorithm is applied, n =6. Obviously the restriction is fallacious and it is only necessary for q< 2'. The author has omitted a few rather important references [2]-[4], not all of which were available at the time of writing; however, they are mentioned for completeness.
Homomorphic Images of Linear Sequential Machines
In this paper we investigate homomorphisms on the state behavior of linear machines and characterize their homomorphic images. These results are then applied to characterize those nonlinear machines which can be realized by larger linear machines.
Identification and Minimization of Linear Machines
This paper is a study of linear machines and their submachines. Methods are presented for finding the reduced form of a given linear machine with or without fixed initial state. A technique is suggested for detecting whether a machine is linear or can be embedded as a submachine in a linear machine. In the latter case a state assignment is produced for the minimum linear realization. Encoded inputs and outputs are assumed, but given machines are not assumed reduced, nor are there any restrictions on the number of states in the given machine or in the linear realization. The method also detects machines that are linearly realizable when constants are available. The main results are that the reduced form of a linear machine is linear and that a linearly realizable machine with r-independent states has an r-dimensional realization.