https://scholars.lib.ntu.edu.tw/handle/123456789/488288
Title: | On the complexity of generating synchronizable test sequences. | Authors: | Liu, Lung-Tien Chen, Gen-Huey Lu, Ching-Sung |
Issue Date: | 1992 | Journal Volume: | 8 | Journal Issue: | 4 | Start page/Pages: | 434-450 | Source: | J. Complexity | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-44049113925&doi=10.1016%2f0885-064X%2892%2990006-W&partnerID=40&md5=42803cafa70a2d6c1de13c42a3b9464c | ISSN: | 0885064X | DOI: | 10.1016/0885-064X(92)90006-W |
Appears in Collections: | 資訊工程學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.