摘要
An optimal IO sequence for the state J and the state K of a protocol, denoted as IO(J,K), is a shortest sequence of inputs which causes the protocol implementation in these two states to generate a different sequence of outputs. Let n and m be the total number of states and transitions, respectively, and d <sub>max</sub> be the largest out-degree of any state; K. Sabnani and A.T. Dahbura proposed an algorithm to compute IO(J,K, J is given and K = 1,2,...,n, with O(n <sup>*</sup> (d <sub>max</sub> ) <sup>n+2</sup> ). This paper proposes a new algorithm to compute IO(J,K), J,K = 1,2,...,n and J<K, with O(m <sup>2</sup> ). © 1991.