Uraz Cengiz TÜRKER

84100

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

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,

PDF
Turkish Journal of Electrical Engineering and Computer Science-Cover
  • ISSN: 1300-0632
  • Yayın Aralığı: Yılda 6 Sayı
  • Yayıncı: TÜBİTAK
Arşiv
Sayıdaki Diğer Makaleler

Rafet DURGUT, Tufan TURACI, Hakan KUTUCU

Khaled Ben SMIDA, Moncef Ben SMIDA, Brahim MRABET

Jyun-yu JHANG, Chengjian LIN, Kuu- YOUNG, Chin-teng LİN

Bundit RUCKVERATHAM, Sathaporn PROMWONG

Muhammad UZAIR, Robert D DONY, Mohsin JAMIL, Khawaja Bilal Ahmad MAHMOOD, Muhammad Nasir KHAN

Prabavathy BALASUNDARAM, Chitra BABU, Pradeep RENGASWAMY

A robust ensemble feature selector based on rank aggregation for developing new VO\textsubscript{2}max prediction models using support vector machines

Fatih ABUT, Mehmet Fatih AKAY, James GEORGE

Belaynesh CHEKOL, Numan ÇELEBİ, Tuğrul TAŞCI

Ümit ŞENTÜRK, Kemal POLAT, İbrahim YÜCEDAĞ

Mohd Rafi LONE, Najeeb-ud-din HAKIM