The Maximum Set of Permissible Behaviors for FSM Networks

Y. Watanabe and Robert K. Brayton

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M93/61
August 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/ERL-93-61.pdf

For systems of interacting finite state machines (FSM's), manual designs sometimes use information derived from the other components to optimize one of them. An associated problem is to find the set of permissible sequential functionalities that can be implemented at a component while preserving the behavior of the total system. Most conventional approaches attempt to find such a set using th notion of don't care sequences, but in general, the complete set of permissible finite state machines are difficult to compute. As a result, only small subsets are derived and used in designing interacting components. However, there is no knowledge of how much optimality is lost using these subsets. This paper proposes a method for computing and representing the complete set of permissible finite state machines. We show that the complete set can be computed and represented by a single non-deterministic finite state machine, called the E-machine. The computation is different from any based on don't care sequences. The transition relation of the E-machine is obtained by a fixed point computation. The procedure has been implemented and initial experimental results are given.

BibTeX citation:

@techreport{Watanabe:M93/61,
    Author = {Watanabe, Y. and Brayton, Robert K.},
    Title = {The Maximum Set of Permissible Behaviors for FSM Networks},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2416.html},
    Number = {UCB/ERL M93/61},
    Abstract = {For systems of interacting finite state machines (FSM's), manual designs sometimes use information derived from the other components to optimize one of them.  An associated problem is to find the set of permissible sequential functionalities that can be implemented at a component while preserving the behavior of the total system.  Most conventional approaches attempt to find such a set using th notion of don't care sequences, but in general, the complete set of permissible finite state machines are difficult to compute.  As a result, only small subsets are derived and used in designing interacting components.  However, there is no knowledge of how much optimality is lost using these subsets.  This paper proposes a method for computing and representing the complete set of permissible finite state machines.  We show that the complete set can be computed and represented by a single non-deterministic finite state machine, called the E-machine.  The computation is different from any based on don't care sequences.  The transition relation of the E-machine is obtained by a fixed point computation.  The procedure has been implemented and initial experimental results are given.}
}

EndNote citation:

%0 Report
%A Watanabe, Y.
%A Brayton, Robert K.
%T The Maximum Set of Permissible Behaviors for FSM Networks
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/ERL M93/61
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2416.html
%F Watanabe:M93/61