On the complexity of generating synchronizable test sequences.
Journal
J. Complexity
Journal Volume
8
Journal Issue
4
Pages
434-450
Date Issued
1992
Author(s)
Liu, Lung-Tien
Chen, Gen-Huey
Lu, Ching-Sung
Abstract
Conformance testing is very important in the framework of protocol engineering. In order to test if the implementation of a protocol conforms to its specification, a test sequence must be generated from the specification, which will be used by an external tester. An external tester includes an active tester and a test responder. When the active tester is far away from the test responder, the test sequence may suffer a synchronization problem. This paper focuses on the complexity of generating synchronizable test sequences. It is shown that generating a minimum-cost synchronizable test sequence is an NP-hard problem. Besides, it is also shown that designing an s-approximation algorithm for the problem is at least as hard as designing an e-approximation algorithm for the asymmetric traveling salesman problem obeying the triangle inequality. Few results on complexity issues of conformance testing appeared before. © 1992.
Type
journal article