Parallelizing heuristics for generating synchronizing sequences
Karahoda, Sertaç and Erenay, Osman Tufan and Kaya, Kamer and Türker, Uraz Cengiz and Yenigün, Hüsnü (2016) Parallelizing heuristics for generating synchronizing sequences. In: 28th IFIP WG 6.1 International Conference on Testing Software and Systems (ICTSS 2016), Graz, Austria
Official URL: http://dx.doi.org/10.1007/978-3-319-47443-4_7
Synchronizing sequences are used in the context of finite state machine based testing in order to initialize an implementation to a particular state. The cubic complexity of even the fastest heuristic algorithms known in the literature to construct a synchronizing sequence can be a problem in practice. In order to scale the performance of synchronizing heuristics, some algorithmic improvements together with a parallel implementation of these heuristics are proposed in this paper. An experimental study is also presented which shows that the improved/parallel implementation can yield a considerable speedup over the sequential implementation.
Repository Staff Only: item control page