Don´t care sequences and the optimization of interacting finite state machines

The authors consider the nature of incomplete specifications for a finite state machine embedded in a network of sequential machines. They show how limited controllability and observability of component machines are expressed in quite different ways. For the input don´t care sequences, a general solution was known. The authors present extensions to it, both in terms of topologies contemplated and in terms of applicability to larger designs. For the output don´t care sequences, they provide a general theory based on the concept of information lossyness and present algorithms to address the related optimization problem in practical cases. The implementation of the proposed techniques in a program called SEQUOIA (sequential optimization of interacting automata) shows that the proposed approach is viable and effective.<>