Parallel brute-force algorithm for deriving reset sequences from deterministic incomplete finite automata

A reset sequence (RS) for a deterministic finite automaton A is an input sequence that brings A to aparticular state regardless of the initial state of A . Incomplete finite automata (FA) are strong in modeling reactivesystems, but despite their importance, there are no works published for deriving RSs from FA. This paper proposes amassively parallel algorithm to derive short RSs from FA. Experimental results reveal that the proposed parallel algorithmcan construct RSs from FA with 16,000,000 states. When multiple GPUs are added to the system the approach canhandle larger FA.

PDF

___

[1] Jourdan G, Ural H, Yenigün H. Reduced checking sequences using unreliable reset. Information Processing Letters 2015; 115 (5): 532-535. doi:10.1016/j.ipl.2015.01.002
[2] Türker UC, Yenigün H. Complexities of some problems related to synchronizing, non-synchronizing and monotonic automata. International Journal of Foundations of Computer Science 2015; 26 (1): 99-122. doi:10.1142/ S0129054115500057
[3] Ananichev DS, Volkov MV. Synchronizing monotonic automata. Theoretical Computer Science 2004; 327 (3): 225- 239.
[4] Eppstein D. Reset sequences for monotonic automata. SIAM Journal of Computing 1990; 19 (3): 500-510.
[5] Natarajan BK. An Algorithmic Approach to the Automated Design of Parts Orienters. In: 27th Annual Symposium on Foundations of Computer Science; Toronto, Canada; 1986. pp. 132-142.
[6] Chow TS. Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering 1978; 4 (3): 178-187.
[7] Boute R. Distinguishing sets for optimal state identification in checking experiments. IEEE Transactions on Computers 1974; 23 (8): 874-877. doi:10.1109/T-C.1974.224043
[8] Petrenko A, Bochmann G. Selecting test sequences for partially-specified nondeterministic finite state machines. In: International Workshop on Protocol Test Systems; London, UK; 1995. pp. 95-110.
[9] Hierons R. Minimizing the number of resets when testing from a finite state machine. Information Processing Letters 2004; 90 (6): 287-292.
[10] Hierons R, Ural H. Generating a checking sequence with a minimum number of reset transitions. Automated Software Engineering 2010; 17 (3): 217-250.
[11] Rezaki A, Ural H. Construction of checking sequences based on characterization sets. Computer Communications 1995; 18 (12): 911-920.
[12] Vasilevskii M. Failure diagnosis of automata. Cybernetics 1973; 9 (4): 653-665. doi:10.1007/BF01068590
[13] Gonenc G. A method for the design of fault detection experiments. IEEE Transactions on Computers 1970: 19 (6): 551-558. doi:10.1109/T-C.1970.222975
[14] Ural H, Wu X, Zhang F. On minimizing the lengths of checking sequences. IEEE Transactions on Computers 1997; 46 (1): 93-99.
[15] Hierons RM, Ural H. Reduced length checking sequences. IEEE Transactions on Computers 2002; 51 (9): 1111-1117.
[16] Benenson Y, Paz-Elizur T, Rivka A, Keinan E, Livneh Z et al. Programmable and autonomous computing machine made of biomolecules. Nature 2001; 414 (6862): 430-434. doi:10.1038/35106533
[17] Benenson Y, Adar R, Paz-Elizur ZLT, Shapiro E. DNA molecule provides a computing machine with both data and fuel. Proceedings of the National Academy of Sciences of the United States 2003; 100 (5): 2191-2196. doi: 10.1073/pnas.0535624100
[18] Stojanovic MN, Stefanovic D. A deoxyribozyme-based molecular automaton. Nature Biotechnology 2003; 21 (9): 1069-1074.
[19] Cherubini A, Gawrychowski P, Kisielewicz A, Piochi B. A combinatorial approach to collapsing words. Mathematical Foundations of Computer Science 2006; 4162: 256-266.
[20] Gill A. Introduction to the Theory of Finite State Machines. New York, NY, USA: McGraw-Hill, 1962.
[21] Hennie FC. Finite-State Models For Logical Machines. New York, NY, USA: Wiley, 1968.
[22] Kohavi Z. Switching and Finite State Automata Theory. New York, NY, USA: McGraw-Hill, 1978.
[23] Roman A. Synchronizing finite automata with short reset words. Applied Mathematics and Computation 2009; 209 (1): 125-136.
[24] Roman A. Genetic algorithm for synchronization. In: Language and Automata Theory and Applications, Third International Conference; Tarragona, Spain; 2009. pp. 684-695.
[25] Roman A. New algorithms for finding short reset sequences in synchronizing automata. In: International Enformatika Conference; Prague, Czech Republic; 2005. pp. 13-17.
[26] Kudłacik R, Roman A, Wagner H. Effective synchronizing algorithms. Expert Systems and Applications 2012; 39 (14): 11746-11757.
[27] Kisielewicz A, Szykuła M. Generating small automata and the Černý conjecture. In: Implementation and Application of Automata; Halifax, Canada; 2013. pp. 340-348. doi:10.1007/978-3-642-39274-0_30
[28] Kisielewicz A, Kowalski J, Szykuła M. A fast algorithm finding the shortest reset words. In: Computing and Combinatorics; Hangzhou, China; 2013. pp. 182-196. doi:10.1007/978-3-642-38768-5_18
[29] Satish N, Harris M, Garland M. Designing efficient sorting algorithms for manycore GPUs. In: IEEE International Symposium on Parallel & Distributed Processing; Rome, Italy; 2009. pp. 1-10.
[30] Merrill D, Garland M, Grimshaw A. Scalable GPU graph traversal. ACM SIGPLAN Notices 2012; 47: 117-128.
[31] Che S, Boyer M, Meng J, Tarjan D, Sheaffer JW et al. A performance study of general-purpose applications on graphics processors using CUDA. Journal of Parallel and Distributed Computing 2008; 68 (10): 1370-1380.
[32] Luo L, Wong M, Hwu WM. An effective GPU implementation of breadth-first search. In: Design Automation Conference; Anaheim, CA, USA; 2010. pp. 52-55.
[33] Harish P, Narayanan P. Accelerating large graph algorithms on the GPU using CUDA. In: High Performance Computing; Goa, India; 2007. pp. 197-208.
[34] Kirk DB, Wen-Mei WH. Programming Massively Parallel Processors: A Hands-On Approach. Oxford, UK: Newnes, 2012.
[35] Mytkowicz T, Musuvathi M, Schulte W. Data-parallel finite-state machines. ACM SIGPLAN Notices 2014; 49 (4): 529-542.
[36] Mytkowicz T, Schulte W. Maine: A Library for Data Parallel Finite Automata. Technical Report. New York, NY, USA: Microsoft Research, 2012.
[37] Hierons RM, Türker UC. Parallel algorithms for testing finite state machines: generating UIO sequences. IEEE Transactions on Computers 2016: 42 (11): 1077-1091.
[38] Hierons RM, Türker UC. Parallel algorithms for testing finite state machines: harmonised state identifiers and characterising sets. IEEE Transactions on Computers 2016; 65 (11): 3370-3383.
[39] Karahoda S, Erenay OT, Kaya K, Türker UC, Yenigün H. Parallelizing heuristics for generating synchronizing sequences. In: Testing Software and Systems; Graz, Austria; 2016. pp. 106-122.
[40] Klingbeil G, Erban R, Giles M, Maini P. Fat versus thin threading approach on GPUs: application to stochastic simulation of chemical reactions. IEEE Transactions on Parallel and Distributed Systems 2012; 23 (2): 280-287.
[41] Hierons RM, Türker UC. Distinguishing sequences for partially specified FSMs. In: NASA Formal Methods; Houston, TX, USA; 2014. pp. 62-76.