Liu, Lung-TienLung-TienLiuChen, Gen-HueyGen-HueyChenLu, Ching-SungChing-SungLu2020-05-042020-05-0419920885064Xhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-44049113925&doi=10.1016%2f0885-064X%2892%2990006-W&partnerID=40&md5=42803cafa70a2d6c1de13c42a3b9464cConformance 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.journal article10.1016/0885-064X(92)90006-W2-s2.0-44049113925https://doi.org/10.1016/0885-064X(92)90006-W