Decomposition of linear sequential machines

Linear sequential machines can sometimes be decomposed into parallel and series connections of smaller linear sequential machines. Necessary and sufficient conditions are given for such decompositions to exist for finite linear sequential machines.Research sponsored by the Air Force Office of Scientific Research, Grant AF-AFOSR 639-67, and by the National Science Foundation, Grant GP-6945     

On the semigroups of linear sequential machines

A new and considerably shorter proof is given to the characterization of the groups of linear nonsingular sequential machines due to Ecker.     

Multivariate control theory in linear sequential machines

This paper presents a unified survey of some modern multivariate control theory aspects and techniques applied to linear sequential machines over a Galois field GF(p), Utilizing the concepts of controllability and observability for a Mealy-type machine the canonical decomposition problem, the state minimization problem, the identification problem, the transformation to canonical form problem, and the controllability/observability problem of combined machines are studied. Then the problem of designing a linear feedback controller for driving any state of a linear machine to the zero state after a minimum number of time steps A(clock periods), as well as the dual problem of designing a time-optimal state reconstructor for the same machine are solved. Finally, the problems of inverting a linear sequential machine and decoupling its inputs and outputs by using state feedforward and feedback are examined. Several examples illustrate the theoretical results.     

Concerning controllability and observability of linear sequential machines

The concept of output–controllability for linear sequential machines over a GF(p) is studied and conditions for k output-controllability are given. Then the concept of k observability is introduced which is the dual of the k state–controllability concept. discussed by Cohn. The duality of controllability and observability is revealed and several examples are studied which illustrate the theoretical results.     

Second common factor of sequential machines

For the synthesis of two or more sequential machines with the same input and specified initial states, Kohavi and Smith [1,2] have investigated the existence of a common factor machine such that, when two machinesM ₁ andM ₂ have a common factor machineM _c ,M ₁ is realized by the cascade connection ofM _c and a snccessor machineM _α, andM ₂ is realized by the cascade connection ofM _c and a snccessor machineM _β. In this paper we study a second common factor machine such that, when two machinesM ₁ andM ₂ have a second common factorM _c,M ₁ is realized by the cascade connection of a front machineM _α andM _c, andM ₂ is realized by the cascade connection of a front machineM _β andM _c.     

MOS networks and fault-tolerant sequential machines

The objective of the present paper is twofold. Firstly the concept of primary partition of an arbitrary Boolean function has been introduced and techniques have been developed to synthesize Boolean functions with two level MOS networks using the concept of primary partition. Special TLM and MTLM modules have been introduced and realisability conditions of Boolean functions with these modules have been developed. Secondly, two algorithms have been described to realise single fault-tolerant sequential machines so that the resulting excitation functions can be implemented by those modules.     

On shift register realization of sequential machines

This paper deals with the modular realization of sequential machines using shift registers as the modules. For a given minimal machine, the minimum number of modules required for its realization has been determined. It is well known that the number of modules required to realize a given machine can sometimes be reduced by realizing a non-minimal machine equivalent to the given minimal one, i.e. by assigning multiple codes to the states of the given minimal machine. This case is dealt with in the second part of the paper.     

Some structural complexities of time-varying sequential machines

Sequential machines with time-variant logic and memory elements are investigated in this paper. Our major efforts are exerted toward considering the isomorphism, minimality, periodicity, time invariance, and convertibility of time-varying sequential machines with an arbitrary set of internal states. It turns out that, if an infinite-state time-varying sequential machine is finite-state realizable, it must eventually bear some sort of a periodic structure and satisfy a time-invariance property on an extended time basis.     

Move limits definition in structural optimization with sequential linear programming. Part II: Numerical examples

A variety of numerical methods have been proposed in literature in purpose to deal with the complexity and non-linearity of structural optimization problems. In practical design, sequential linear programming (SLP) is very popular because of its inherent simplicity and because linear solvers (e.g. Simplex) are easily available. However, SLP performance is sensitive to the definition of proper move limits for the design variables which task itself often involves considerable heuristics. This research presents a new SLP algorithm (LESLP) that implements an advanced technique for defining the move limits. The linearization error sequential linear programming (LESLP) algorithm is formulated so to overcome the traditional limitations of the SLP method. In a companion paper [Comput. Struct. 81 (2003) 197] the basics of the LESLP formulation along with a guide to programming are provided.The new algorithm is successfully tested in weight minimisation problems of truss structures with up to hundreds of design variables and thousands of constraints: sizing and configuration problems are considered. Optimization problems of non-truss structures are also presented. The numerical efficiency, advantages and drawbacks of LESLP are discussed and compared to those of other SLP algorithms recently published or implemented in commercial software packages.     

Minimal coverings for incompletely specified sequential machines

Summary In the literature the problem of finding minimal realizations for incompletely specified machines has been treated in a number of different ways. Solutions to this problem depend on the precise definition of what minimal realization means in this case. If the behaviour of a state is definied as its related partial input-output function then the behaviour of one machine A can cover the behaviour of another machine B if it contains better definied I/O functions for all states of B. Finding a minimal covering in this case is known to be NP-complete. We develop an algebraic treatment of the problem and give a homomorphic characterization of the covering-relation. The construction of state-splitting is also characterized as a special morphism. Then a heuristic method is proposed for finding minimal coverings.     

Static state feedback control of asynchronous sequential machines

Static controllers, which consist of logical gates with no memory elements, form the simplest class of controllers for asynchronous sequential machines. This paper presents necessary and sufficient conditions for the existence of static state feedback controllers that control a given asynchronous sequential machine so as to match a specified model. The process of designing static state feedback controllers is described.     

Input/output control of asynchronous sequential machines

The problem of controlling a finite-state asynchronous sequential machine is examined. Main consideration is given to input/output control, where access to the state of the machine is not available. The objective is to use output feedback to control the machine so as to match a prescribed model. It is shown that necessary and sufficient conditions for the existence of appropriate controllers can be stated in terms of a simple comparison of two numerical matrices. Whenever controllers exist, algorithms for their design are outlined.     

On the control of sequential machines with disturbances

The problem of controlling a sequential machine under the influence of disturbances is considered. A methodology is developed for the design of controllers that guarantees that the effect of a 'small' disturbance on the performance of the controlled machine remains 'small'. The methodology is based on a theory of fraction representations of sequential machines reminiscent of the general theory of fraction representations of nonlinear systems.