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

[thumbnail of This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)] PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing))
llncs.pdf

Download (1MB)

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.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Engineering controlled terms: Heuristic algorithms; Software testing
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Q Science > QA Mathematics
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences > Basic Sciences > Mathematics
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 13 Nov 2016 18:17
Last Modified: 26 Apr 2022 09:24
URI: https://research.sabanciuniv.edu/id/eprint/30405

Actions (login required)

View Item
View Item