An FPGA based approach for Černý conjecture falsification

Koca, Çağla (2018) An FPGA based approach for Černý conjecture falsification. [Thesis]

[thumbnail of 10207511_CaglaKoca.pdf] PDF

Download (1MB)


A synchronizing sequence for an automaton is a special input sequence that sends all states of the automaton to the same state. J. Černý conjectured that the length of the shortest synchronizing sequence of an automaton with n states cannot be greater than (n-1)2, which is known today as the Černý conjecture. This half-a-century old conjecture is still open and it is considered to be the most long-standing open problem in the combinatorial theory of finite state automata. One research line that has been pursued in the literature is to check if the conjecture holds for a fixed number of states n, by considering all automata with n states and checking if any of these automata falsifies the conjecture. This is a computationally intensive task, even for automata up to a dozen of states and only two input symbols. To accelerate the search parallel computation approaches using multicore CPUs have been tried before. In this thesis, we study the use of FPGAs to accelerate the search for an automaton falsifying the Černý conjecture. We present a design to calculate iii the minimum length synchronizing sequence of a finite state automaton. The proposed design is implemented with the parallel computing capability of hardware designs while optimizing the time performance.
Item Type: Thesis
Uncontrolled Keywords: FPGA. -- Synchronizing sequences. -- Černý conjecture. -- APKD. -- Sıfırlama dizileri. -- Černý sanıtı.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 01 Oct 2018 13:12
Last Modified: 26 Apr 2022 10:25

Actions (login required)

View Item
View Item