Synchronizing heuristics: speeding up the slowest

Altun, Ömer Faruk and Atam, Kamil Tolga and Karahoda, Sertaç and Kaya, Kamer (2017) Synchronizing heuristics: speeding up the slowest. In: The 29th IFIP International Conference on Testing Software and Systems, St-Petersburg (Accepted/In Press)

[thumbnail of SpeedingUpTheSlowest.pdf] PDF
SpeedingUpTheSlowest.pdf
Restricted to Repository staff only

Download (554kB) | Request a copy

Abstract

Computing a shortest synchronizing word of an automaton is an NP–hard problem. Therefore, heuristics are used to compute short synchronizing words. SynchroP is among the best heuristics in the literature in terms of word lengths. The heuristic and its variants such as SynchroPL have been frequently used as a baseline to judge the quality of the words generated by the new heuristics. Although, its quality is good, the heuristics are significantly slow especially compared to much cheaper heuristics such as Greedy and Cycle. This makes them in- feasible for large-scale automatons. In this paper, we show how one can improve the time performance of SynchroP and its variants by avoiding unnecessary computations which makes these heuristics more competitive than they already are. Our experimental results show that for 2500 states, SynchroP can be made 70–160× faster, via the proposed optimizations. In particular, for 2500 states and 32 letters, the SynchroP execution reduces to 66 seconds from 4745 seconds. Furthermore, the suggested optimizations become more effective as the number of states in the automata increase.
Item Type: Papers in Conference Proceedings
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 20 Aug 2017 16:09
Last Modified: 26 Apr 2022 09:27
URI: https://research.sabanciuniv.edu/id/eprint/33004

Actions (login required)

View Item
View Item