Synchronizing Sequences

Designing and developing a large-scale, correct, and complex system is not an easy task. Several validation techniques have been proposed to build some confidence in the developed systems, but testing stands out as one of the most practical one. To automate the testing process, there has been much interest in testing with Finite State Machines (FSMs). To employ FSMs for testing, one needs to bring the system under test (SUT) to a particular state. It is quite easy to do that when a trusted reset input exists in the SUT. However, such a reset input is not always available.

A synchronizing sequence (also known as a reset sequence or a reset word) for an FSM is a sequence of inputs such that when applied to the FSM, the machine ends up in a particular state no matter at which state it initially is. Therefore a synchronizing sequence is a compound reset input for a machine. The shorter the synchronizing sequence is, the quicker is the synchronization process. Hence, shorter reset sequences are desirable in terms of synchronization time and energy spent. However, the problem of finding a shortest synchronizing sequence is NP-hard. It is conjectured that for a synchronizing automaton with n states, the length of the shortest synchronizing sequence is at most (n-1)², which is known as the Černý Conjecture in the literature. Posed half a century ago, the conjecture is still open. The motivation to study synchronizing sequences comes not only from the testing domain but also from different fields including automata theory, robotics, bio-computing, set theory, propositional calculus, model-based testing, and many more.

Due to the hardness of finding a shortest sequence, there exist heuristics in the literature, known as synchronizing heuristics, to compute short synchronizing words. Among such heuristics are Greedy, Cycle, SynchroP, SynchroPL, and FastSynchro. In this project, we focus on designing and implementing novel and existing parallel synchronizing sequence heuristics for large-scale and/or slowly synchronizing automata on multicore CPUs and manycore GPUs.

Related Publications:

• Synchronizing billion-scale automata. MK Taş, K Kaya, H Yenigün. Information Sciences 574, 162-175, 2021
• *Boosting expensive synchronizing heuristics, NE Saraç, ÖF Altun, KT Atam, S Karahoda, K Kaya, H Yenigün. Expert Systems with Applications 167, 114203, 2021
• Multicore and manycore parallelization of cheap synchronizing sequence heuristics. S Karahoda, OT Erenay, K Kaya, UC Türker, H Yenigün. Journal of Parallel and Distributed Computing 140, 13-24, 2020
• Using synchronizing heuristics to construct homing sequences. B Çirişci, MY Emek, E Sorguç, K Kaya, H Yenigün. 7th International Conference on Model-Driven Engineering and Software Development (MODELSWARD 2019), 364-371, 2019
• Synchronizing heuristics: Speeding up the fastest. S Karahoda, K Kaya, H Yenigün. Expert Systems with Applications 94, 265-275, 2018
• Synchronizing Heuristics for Weakly Connected Automata with Various Topologies. B Cirisci, B Sevilmiş, EY Sivri, PK Karaçam, K Kaya, H Yenigün. International Conference on Model-Driven Engineering and Software Development, 475-493, 2018
• Using Structure of Automata for Faster Synchronizing Heuristics. B Cirisci, MK Kahraman, CU Yildirimoglu, K Kaya, H Yenigün. MODELSWARD, 544-551, 2018
• Synchronizing heuristics: speeding up the slowest. ÖF Altun, KT Atam, S Karahoda, K Kaya. IFIP International Conference on Testing Software and Systems, 243-256, 2017
• Parallelizing heuristics for generating synchronizing sequences. S Karahoda, OT Erenay, K Kaya, UC Türker, H Yenigün. IFIP International Conference on Testing Software and Systems, 106-122, 2016