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

Abstract

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.