https://scholars.lib.ntu.edu.tw/handle/123456789/488288
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Liu, Lung-Tien | en_US |
dc.contributor.author | Chen, Gen-Huey | en_US |
dc.contributor.author | Lu, Ching-Sung | en_US |
dc.creator | Liu, Lung-Tien;Chen, Gen-Huey;Lu, Ching-Sung | - |
dc.date.accessioned | 2020-05-04T07:54:24Z | - |
dc.date.available | 2020-05-04T07:54:24Z | - |
dc.date.issued | 1992 | - |
dc.identifier.issn | 0885064X | - |
dc.identifier.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 | - |
dc.description.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. | - |
dc.relation.ispartof | J. Complexity | - |
dc.title | On the complexity of generating synchronizable test sequences. | en_US |
dc.type | journal article | en |
dc.identifier.doi | 10.1016/0885-064X(92)90006-W | - |
dc.identifier.scopus | 2-s2.0-44049113925 | - |
dc.identifier.url | https://doi.org/10.1016/0885-064X(92)90006-W | - |
dc.relation.pages | 434-450 | - |
dc.relation.journalvolume | 8 | - |
dc.relation.journalissue | 4 | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
item.openairetype | journal article | - |
item.grantfulltext | none | - |
item.cerifentitytype | Publications | - |
item.fulltext | no fulltext | - |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。