摘要
Testing if a multi-party protocol implementation conforms to the specification is achieved by a testing system with k testers (where k ≥ 2), among which synchronization problems are encountered. This paper proposes a new model for test sequence generation, which considers both the costs of input/output operations and external synchronization operations. The multiplex digraph model is transformed from a given finite state machine representation of the protocol (with n states, m transitions and k is considered as constant) using an O(m 2 ) algorithm, and can represent the testing process cost of an arbitrarily-configured testing system. Application of the model includes: (1) an O(m 2 ) algorithm for generating the minimum-cost synchronizable transfer sequence, improving an earlier exponential-time backtracking algorithm; (2) an O(m 2 ) algorithm for generating the synchronizable test sequence based on the T-method, improving an earlier exponential-time backtracking algorithm; (3) an O(n·m 2 ) algorithm for generating the synchronizable test sequence based on the overlapping U-method, which is an uninvestigated result even for k = 2. © 1998 Elsevier Science B.V.