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.
Linearity of Sequential Machines
A sequential machine is defined to be linear if its next-state function and output function are linear transformations from their domains (vector spaces) to their ranges (also vector spaces). It is shown that this definition is equivalent to those given by other authors. Based on this definition, a set of necessary and sufficient conditions for the flow table of a sequential machine to be linear is obtained. Many properties of the flow table of a linear sequential machine are found, and in many cases they form very simple tests for the linearity of a flow table. A general procedure for testing the linearity of a flow table is established. This procedure, including the coding of the states, inputs, and outputs, either ends with a linear realization of the flow table with the minimum possible numbers of state variables, input variables, and output variables, or detects that such a linear realization for the flow table is impossible. The type of sequential machine considered in this paper is deterministic and synchronous, and both Moore model and Mealy model are studied in detail. The linearity of incompletely specified sequential machines is also discussed.
The parallel waveform relaxation stochastic Runge–Kutta method for stochastic differential equations
For large-scale non-autonomous Stratonovich stochastic differential equations, we study a very general parallel waveform relaxation process which is on the basis of stochastic Runge–Kutta (SRK) method of mean-square order 1.0 in this literature. The convergence of the whole parallel numerical iterative scheme can be guaranteed and the scheme provides better properties in terms of decreasing the load of the computation and operating speed. At the same time, the related limit method is also introduced as the continuous approximation derived from the iterative scheme. In the approximation interval, it is worth noting that the mean-square order of the parallel numerical iterative scheme can be kept consistent with the previous SRK method at any arbitrary time point, not just at discrete points. Some numerical simulations are presented to elaborate the computing efficiency of the parallel numerical iterative scheme.