Decision problems for interacting finite state machines
D. Drusinsky-Yoresh · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1991
Given a system of n interacting finite state machines (FSMs) and a state configuration, the reachability problem is to examine whether this configuration is reachable within the system. An investigation is made of the complexity of this decision problem and three of its derivatives, namely, (1) verifying system determination, (2) testing for the existence of unspecified inputs to any FSM within the system, and (3) testing for exclusiveness of two intra-FSM signals. It is proved that these problems are all PSPACE-complete. The effect of these problems on the state assignment process for concurrent systems of interacting FSMs is also shown.>