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

Authors

URAZ CENGİZ TÜRKER

DOI

10.3906/elk-1809-1

Abstract

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

Keywords

Finite automata, incomplete finite automata, brute-force approach reset sequences, GPGPU programming

First Page

3544

Last Page

3556

Recommended Citation

TÜRKER, URAZ CENGİZ (2019) "Parallel brute-force algorithm for deriving reset sequences from deterministic incomplete finite automata," Turkish Journal of Electrical Engineering and Computer Sciences: Vol. 27: No. 5, Article 20. https://doi.org/10.3906/elk-1809-1
Available at: https://journals.tubitak.gov.tr/elektrik/vol27/iss5/20