Parallelizing Heuristics for Generating Synchronizing Sequences

Abstract : 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.
Liste complète des métadonnées

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01643717
Contributor : Hal Ifip <>
Submitted on : Tuesday, November 21, 2017 - 3:52:58 PM
Last modification on : Tuesday, November 21, 2017 - 3:56:00 PM

File

419911_1_En_7_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Sertaç Karahoda, Osman Erenay, Kamer Kaya, Uraz Türker, Husnu Yenigun. Parallelizing Heuristics for Generating Synchronizing Sequences. 28th IFIP International Conference on Testing Software and Systems (ICTSS), Oct 2016, Graz, Austria. pp.106-122, ⟨10.1007/978-3-319-47443-4_7⟩. ⟨hal-01643717⟩

Share

Metrics

Record views

34

Files downloads

11