Model matching for asynchronous sequential machines

The presence of critical races causes an asynchronous sequential machine to produce unpredicted and undesired behavior. This has been a major problem since the early development of asynchronous sequential machines. Although many methods are available for the design of race free machines, the literature seems to contain no techniques for eliminating the negative effects of races in existing machines.We investigated the problem of eliminating the effects of critical races on asynchronous sequential machines by using feedback controllers. In addition to eliminating the effects of races, these controllers also transform the system to match the behavior of a prescribed model.Our study addressed machines in which the state is provided as output (input/state machines) as well as machines whose state is not provided as output (input/output machines). In the case of asynchronous input/state machines, the controller works as a state-feedback controller. For asynchronous input/output machines, the controller decomposes into two units: an observer and a state-feedback control unit. The observer estimates the state of the system and provides this information to the control unit, which uses it to correct the behavior of the controlled machine. This decomposition of the controller into an observer and a state feedback control unit generalizes the well-known separation principle of linear control theory to the case of asynchronous machines.The model matching problem is resolved for both deterministic machines and machines affected by a critical race. For asynchronous machines affected by races, the proposed solution of the model matching problem yields a machine whose input/output behavior is deterministic and simulates the behavior of a prescribed desirable model. This strategy overcomes the uncertainty induced by the race and corrects other undesirable aspects of the machine's behavior.The results presented in the dissertation include necessary and sufficient conditions for the existence of controllers as well as algorithms for their construction (whenever the controllers exist). The necessary and sufficient conditions are presented in terms of certain matrix inequalities.